diff --git a/libcxx/include/__string b/libcxx/include/__string --- a/libcxx/include/__string +++ b/libcxx/include/__string @@ -374,7 +374,7 @@ char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT { return __libcpp_is_constant_evaluated() - ? __move_constexpr(__s1, __s2, __n) + ? _VSTD::__move_constexpr(__s1, __s2, __n) : __n == 0 ? __s1 : (char_type*)memmove(__s1, __s2, __n); } static inline _LIBCPP_CONSTEXPR_AFTER_CXX17 @@ -382,14 +382,14 @@ { _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); return __libcpp_is_constant_evaluated() - ? __copy_constexpr(__s1, __s2, __n) + ? _VSTD::__copy_constexpr(__s1, __s2, __n) : __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n); } static inline _LIBCPP_CONSTEXPR_AFTER_CXX17 char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT { return __libcpp_is_constant_evaluated() - ? __assign_constexpr(__s, __n, __a) + ? _VSTD::__assign_constexpr(__s, __n, __a) : __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n); } @@ -477,7 +477,7 @@ char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT { return __libcpp_is_constant_evaluated() - ? __move_constexpr(__s1, __s2, __n) + ? _VSTD::__move_constexpr(__s1, __s2, __n) : __n == 0 ? __s1 : wmemmove(__s1, __s2, __n); } static inline _LIBCPP_CONSTEXPR_AFTER_CXX17 @@ -485,14 +485,14 @@ { _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); return __libcpp_is_constant_evaluated() - ? __copy_constexpr(__s1, __s2, __n) + ? _VSTD::__copy_constexpr(__s1, __s2, __n) : __n == 0 ? __s1 : wmemcpy(__s1, __s2, __n); } static inline _LIBCPP_CONSTEXPR_AFTER_CXX17 char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT { return __libcpp_is_constant_evaluated() - ? __assign_constexpr(__s, __n, __a) + ? _VSTD::__assign_constexpr(__s, __n, __a) : __n == 0 ? __s : wmemset(__s, __a, __n); } static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT @@ -610,7 +610,7 @@ char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT { return __libcpp_is_constant_evaluated() - ? __move_constexpr(__s1, __s2, __n) + ? _VSTD::__move_constexpr(__s1, __s2, __n) : __n == 0 ? __s1 : (char_type*)memmove(__s1, __s2, __n); } @@ -619,7 +619,7 @@ { _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); return __libcpp_is_constant_evaluated() - ? __copy_constexpr(__s1, __s2, __n) + ? _VSTD::__copy_constexpr(__s1, __s2, __n) : __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n); } @@ -627,7 +627,7 @@ char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT { return __libcpp_is_constant_evaluated() - ? __assign_constexpr(__s, __n, __a) + ? _VSTD::__assign_constexpr(__s, __n, __a) : __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n); } diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -1707,7 +1707,7 @@ _OutputIterator __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - return __copy_constexpr(__first, __last, __result); + return _VSTD::__copy_constexpr(__first, __last, __result); } template @@ -1733,10 +1733,10 @@ { if (__libcpp_is_constant_evaluated()) { return _VSTD::__copy_constexpr( - __unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result)); + _VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result)); } else { return _VSTD::__copy( - __unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result)); + _VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result)); } } @@ -1757,7 +1757,7 @@ _OutputIterator __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result) { - return __copy_backward_constexpr(__first, __last, __result); + return _VSTD::__copy_backward_constexpr(__first, __last, __result); } template @@ -1786,13 +1786,13 @@ _BidirectionalIterator2 __result) { if (__libcpp_is_constant_evaluated()) { - return _VSTD::__copy_backward_constexpr(__unwrap_iter(__first), - __unwrap_iter(__last), - __unwrap_iter(__result)); + return _VSTD::__copy_backward_constexpr(_VSTD::__unwrap_iter(__first), + _VSTD::__unwrap_iter(__last), + _VSTD::__unwrap_iter(__result)); } else { - return _VSTD::__copy_backward(__unwrap_iter(__first), - __unwrap_iter(__last), - __unwrap_iter(__result)); + return _VSTD::__copy_backward(_VSTD::__unwrap_iter(__first), + _VSTD::__unwrap_iter(__last), + _VSTD::__unwrap_iter(__result)); } } @@ -1876,7 +1876,7 @@ _OutputIterator __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - return __move_constexpr(__first, __last, __result); + return _VSTD::__move_constexpr(__first, __last, __result); } template @@ -1890,7 +1890,7 @@ __move(_Tp* __first, _Tp* __last, _Up* __result) { if (__libcpp_is_constant_evaluated()) - return __move_constexpr(__first, __last, __result); + return _VSTD::__move_constexpr(__first, __last, __result); const size_t __n = static_cast(__last - __first); if (__n > 0) _VSTD::memmove(__result, __first, __n * sizeof(_Up)); @@ -1902,7 +1902,7 @@ _OutputIterator move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result)); + return _VSTD::__move(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result)); } // move_backward @@ -1924,7 +1924,7 @@ _OutputIterator __move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - return __move_backward_constexpr(__first, __last, __result); + return _VSTD::__move_backward_constexpr(__first, __last, __result); } template @@ -1938,7 +1938,7 @@ __move_backward(_Tp* __first, _Tp* __last, _Up* __result) { if (__libcpp_is_constant_evaluated()) - return __move_backward_constexpr(__first, __last, __result); + return _VSTD::__move_backward_constexpr(__first, __last, __result); const size_t __n = static_cast(__last - __first); if (__n > 0) { @@ -1954,7 +1954,7 @@ move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) { - return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result)); + return _VSTD::__move_backward(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result)); } // iter_swap @@ -3439,7 +3439,7 @@ // F????????????????? // f m l typedef typename add_lvalue_reference<_Predicate>::type _PredRef; - _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit); + _ForwardIterator __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit); // TTTFFFFF?????????? // f ff m l // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true @@ -3454,7 +3454,7 @@ } // TTTFFFFFTTTF?????? // f ff m m1 l - __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit); + __second_false = _VSTD::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit); __second_half_done: // TTTFFFFFTTTTTFFFFF // f ff m sf l @@ -3496,7 +3496,7 @@ __p = _VSTD::get_temporary_buffer(__len); __h.reset(__p.first); } - return __stable_partition::type> + return _VSTD::__stable_partition::type> (__first, __last, __pred, __len, __p, forward_iterator_tag()); } @@ -3582,7 +3582,7 @@ // F???TFFF?????????T // f m1 m l typedef typename add_lvalue_reference<_Predicate>::type _PredRef; - __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit); + __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit); __first_half_done: // TTTFFFFF?????????T // f ff m l @@ -3599,7 +3599,7 @@ } // TTTFFFFFTTTF?????T // f ff m m1 l - __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit); + __second_false = _VSTD::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit); __second_half_done: // TTTFFFFFTTTTTFFFFF // f ff m sf l @@ -3644,7 +3644,7 @@ __p = _VSTD::get_temporary_buffer(__len); __h.reset(__p.first); } - return __stable_partition::type> + return _VSTD::__stable_partition::type> (__first, __last, __pred, __len, __p, bidirectional_iterator_tag()); } @@ -3653,7 +3653,7 @@ _ForwardIterator stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) { - return __stable_partition::type> + return _VSTD::__stable_partition::type> (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); } @@ -3751,7 +3751,7 @@ __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _Compare __c) { - unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c); + unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c); if (__c(*__x4, *__x3)) { swap(*__x3, *__x4); @@ -3778,7 +3778,7 @@ __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) { - unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c); + unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c); if (__c(*__x5, *__x4)) { swap(*__x4, *__x5); @@ -3843,7 +3843,7 @@ { typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; _RandomAccessIterator __j = __first+2; - __sort3<_Compare>(__first, __first+1, __j, __comp); + _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp); for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) { if (__comp(*__i, *__j)) @@ -3887,7 +3887,7 @@ } typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; _RandomAccessIterator __j = __first+2; - __sort3<_Compare>(__first, __first+1, __j, __comp); + _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp); const unsigned __limit = 8; unsigned __count = 0; for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) @@ -4247,7 +4247,7 @@ lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) { typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; - return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp); + return _VSTD::__lower_bound<_Comp_ref>(__first, __last, __value_, __comp); } template @@ -4291,7 +4291,7 @@ upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) { typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; - return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp); + return _VSTD::__upper_bound<_Comp_ref>(__first, __last, __value_, __comp); } template @@ -4332,8 +4332,8 @@ _ForwardIterator __mp1 = __m; return pair<_ForwardIterator, _ForwardIterator> ( - __lower_bound<_Compare>(__first, __m, __value_, __comp), - __upper_bound<_Compare>(++__mp1, __last, __value_, __comp) + _VSTD::__lower_bound<_Compare>(__first, __m, __value_, __comp), + _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value_, __comp) ); } } @@ -4347,7 +4347,7 @@ equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return __equal_range<_Comp_ref>(__first, __last, __value_, __comp); + return _VSTD::__equal_range<_Comp_ref>(__first, __last, __value_, __comp); } template @@ -4367,7 +4367,7 @@ bool __binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) { - __first = __lower_bound<_Compare>(__first, __last, __value_, __comp); + __first = _VSTD::__lower_bound<_Compare>(__first, __last, __value_, __comp); return __first != __last && !__comp(__value_, *__first); } @@ -4378,7 +4378,7 @@ binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return __binary_search<_Comp_ref>(__first, __last, __value_, __comp); + return _VSTD::__binary_search<_Comp_ref>(__first, __last, __value_, __comp); } template @@ -4483,7 +4483,7 @@ value_type* __p = __buff; for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr(), (void) ++__i, (void) ++__p) ::new(__p) value_type(_VSTD::move(*__i)); - __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp); + _VSTD::__half_inplace_merge(__buff, __p, __middle, __last, __first, __comp); } else { @@ -4492,9 +4492,9 @@ ::new(__p) value_type(_VSTD::move(*__i)); typedef reverse_iterator<_BidirectionalIterator> _RBi; typedef reverse_iterator _Rv; - __half_inplace_merge(_Rv(__p), _Rv(__buff), - _RBi(__middle), _RBi(__first), - _RBi(__last), __invert<_Compare>(__comp)); + _VSTD::__half_inplace_merge(_Rv(__p), _Rv(__buff), + _RBi(__middle), _RBi(__first), + _RBi(__last), _VSTD::__invert<_Compare>(__comp)); } } @@ -4512,7 +4512,7 @@ if (__len2 == 0) return; if (__len1 <= __buff_size || __len2 <= __buff_size) - return __buffered_inplace_merge<_Compare> + return _VSTD::__buffered_inplace_merge<_Compare> (__first, __middle, __last, __comp, __len1, __len2, __buff); // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0 for (; true; ++__first, (void) --__len1) @@ -4540,7 +4540,7 @@ __len21 = __len2 / 2; __m2 = __middle; _VSTD::advance(__m2, __len21); - __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp); + __m1 = _VSTD::__upper_bound<_Compare>(__first, __middle, *__m2, __comp); __len11 = _VSTD::distance(__first, __m1); } else @@ -4555,7 +4555,7 @@ __len11 = __len1 / 2; __m1 = __first; _VSTD::advance(__m1, __len11); - __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp); + __m2 = _VSTD::__lower_bound<_Compare>(__middle, __last, *__m1, __comp); __len21 = _VSTD::distance(__middle, __m2); } difference_type __len12 = __len1 - __len11; // distance(__m1, __middle) @@ -4567,8 +4567,8 @@ // merge smaller range with recurisve call and larger with tail recursion elimination if (__len11 + __len21 < __len12 + __len22) { - __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); -// __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); + _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); +// _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); __first = __middle; __middle = __m2; __len1 = __len12; @@ -4576,8 +4576,8 @@ } else { - __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); -// __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); + _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); +// _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); __last = __middle; __middle = __m1; __len1 = __len11; @@ -4726,14 +4726,14 @@ } if (__len <= 8) { - __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp); + _VSTD::__insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp); return; } typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; _RandomAccessIterator __m = __first1 + __l2; - __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2); - __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2); - __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp); + _VSTD::__stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2); + _VSTD::__stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2); + _VSTD::__merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp); } template @@ -4762,7 +4762,7 @@ } if (__len <= static_cast(__stable_sort_switch::value)) { - __insertion_sort<_Compare>(__first, __last, __comp); + _VSTD::__insertion_sort<_Compare>(__first, __last, __comp); return; } typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; @@ -4771,21 +4771,21 @@ { __destruct_n __d(0); unique_ptr __h2(__buff, __d); - __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff); + _VSTD::__stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff); __d.__set(__l2, (value_type*)nullptr); - __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2); + _VSTD::__stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2); __d.__set(__len, (value_type*)nullptr); - __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp); -// __merge<_Compare>(move_iterator(__buff), -// move_iterator(__buff + __l2), -// move_iterator<_RandomAccessIterator>(__buff + __l2), -// move_iterator<_RandomAccessIterator>(__buff + __len), -// __first, __comp); + _VSTD::__merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp); +// _VSTD::__merge<_Compare>(move_iterator(__buff), +// move_iterator(__buff + __l2), +// move_iterator<_RandomAccessIterator>(__buff + __l2), +// move_iterator<_RandomAccessIterator>(__buff + __len), +// __first, __comp); return; } - __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size); - __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); - __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); + _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size); + _VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); + _VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); } template @@ -4804,7 +4804,7 @@ __h.reset(__buf.first); } typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); + _VSTD::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); } template @@ -4908,7 +4908,7 @@ push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first); + _VSTD::__sift_up<_Comp_ref>(__first, __last, __comp, __last - __first); } template @@ -4985,7 +4985,7 @@ if (__len > 1) { swap(*__first, *--__last); - __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first); + _VSTD::__sift_down<_Compare>(__first, __last, __comp, __len - 1, __first); } } @@ -4995,7 +4995,7 @@ pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first); + _VSTD::__pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first); } template @@ -5019,7 +5019,7 @@ // start from the first parent, there is no need to consider children for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) { - __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start); + _VSTD::__sift_down<_Compare>(__first, __last, __comp, __n, __first + __start); } } } @@ -5030,7 +5030,7 @@ make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - __make_heap<_Comp_ref>(__first, __last, __comp); + _VSTD::__make_heap<_Comp_ref>(__first, __last, __comp); } template @@ -5049,7 +5049,7 @@ { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n) - __pop_heap<_Compare>(__first, __last, __comp, __n); + _VSTD::__pop_heap<_Compare>(__first, __last, __comp, __n); } template @@ -5058,7 +5058,7 @@ sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - __sort_heap<_Comp_ref>(__first, __last, __comp); + _VSTD::__sort_heap<_Comp_ref>(__first, __last, __comp); } template @@ -5076,17 +5076,17 @@ __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp) { - __make_heap<_Compare>(__first, __middle, __comp); + _VSTD::__make_heap<_Compare>(__first, __middle, __comp); typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first; for (_RandomAccessIterator __i = __middle; __i != __last; ++__i) { if (__comp(*__i, *__first)) { swap(*__i, *__first); - __sift_down<_Compare>(__first, __middle, __comp, __len, __first); + _VSTD::__sift_down<_Compare>(__first, __middle, __comp, __len, __first); } } - __sort_heap<_Compare>(__first, __middle, __comp); + _VSTD::__sort_heap<_Compare>(__first, __middle, __comp); } template @@ -5096,7 +5096,7 @@ _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - __partial_sort<_Comp_ref>(__first, __middle, __last, __comp); + _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp); } template @@ -5120,15 +5120,15 @@ { for (; __first != __last && __r != __result_last; ++__first, (void) ++__r) *__r = *__first; - __make_heap<_Compare>(__result_first, __r, __comp); + _VSTD::__make_heap<_Compare>(__result_first, __r, __comp); typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first; for (; __first != __last; ++__first) if (__comp(*__first, *__result_first)) { *__result_first = *__first; - __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first); + _VSTD::__sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first); } - __sort_heap<_Compare>(__result_first, __r, __comp); + _VSTD::__sort_heap<_Compare>(__result_first, __r, __comp); } return __r; } @@ -5140,7 +5140,7 @@ _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp); + return _VSTD::__partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp); } template @@ -5186,7 +5186,7 @@ } if (__len <= __limit) { - __selection_sort<_Compare>(__first, __last, __comp); + _VSTD::__selection_sort<_Compare>(__first, __last, __comp); return; } // __len > __limit >= 3 @@ -5210,7 +5210,7 @@ if (__i == --__j) { // *__first == *__m, *__m <= all other elements - // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) + // Partition instead into [__first, __i) == *__first and *__first < [__i, __last) ++__i; // __first + 1 __j = __last; if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) @@ -5248,8 +5248,8 @@ // The first part is sorted, if (__nth < __i) return; - // __nth_element the secod part - // __nth_element<_Compare>(__i, __nth, __last, __comp); + // __nth_element the second part + // _VSTD::__nth_element<_Compare>(__i, __nth, __last, __comp); __first = __i; goto __restart; } @@ -5331,12 +5331,12 @@ // __nth_element on range containing __nth if (__nth < __i) { - // __nth_element<_Compare>(__first, __nth, __i, __comp); + // _VSTD::__nth_element<_Compare>(__first, __nth, __i, __comp); __last = __i; } else { - // __nth_element<_Compare>(__i+1, __nth, __last, __comp); + // _VSTD::__nth_element<_Compare>(__i+1, __nth, __last, __comp); __first = ++__i; } } @@ -5348,7 +5348,7 @@ nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - __nth_element<_Comp_ref>(__first, __nth, __last, __comp); + _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp); } template @@ -5384,7 +5384,7 @@ _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); + return _VSTD::__includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); } template @@ -5432,7 +5432,7 @@ _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); + return _VSTD::__set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); } template @@ -5478,7 +5478,7 @@ _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); + return _VSTD::__set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); } template @@ -5526,7 +5526,7 @@ _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); + return _VSTD::__set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); } template @@ -5579,7 +5579,7 @@ _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); + return _VSTD::__set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); } template @@ -5618,7 +5618,7 @@ _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); + return _VSTD::__lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); } template @@ -5668,7 +5668,7 @@ next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return __next_permutation<_Comp_ref>(__first, __last, __comp); + return _VSTD::__next_permutation<_Comp_ref>(__first, __last, __comp); } template @@ -5715,7 +5715,7 @@ prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return __prev_permutation<_Comp_ref>(__first, __last, __comp); + return _VSTD::__prev_permutation<_Comp_ref>(__first, __last, __comp); } template diff --git a/libcxx/include/locale b/libcxx/include/locale --- a/libcxx/include/locale +++ b/libcxx/include/locale @@ -873,8 +873,8 @@ const numpunct<_CharT>& __np = use_facet >(__iob.getloc()); typedef typename numpunct<_CharT>::string_type string_type; const string_type __names[2] = {__np.truename(), __np.falsename()}; - const string_type* __i = __scan_keyword(__b, __e, __names, __names+2, - __ct, __err); + const string_type* __i = _VSTD::__scan_keyword(__b, __e, __names, __names+2, + __ct, __err); __v = __i == __names; return __b; } @@ -1912,7 +1912,7 @@ { // Note: ignoring case comes from the POSIX strptime spec const string_type* __wk = this->__weeks(); - ptrdiff_t __i = __scan_keyword(__b, __e, __wk, __wk+14, __ct, __err, false) - __wk; + ptrdiff_t __i = _VSTD::__scan_keyword(__b, __e, __wk, __wk+14, __ct, __err, false) - __wk; if (__i < 14) __w = __i % 7; } @@ -1926,7 +1926,7 @@ { // Note: ignoring case comes from the POSIX strptime spec const string_type* __month = this->__months(); - ptrdiff_t __i = __scan_keyword(__b, __e, __month, __month+24, __ct, __err, false) - __month; + ptrdiff_t __i = _VSTD::__scan_keyword(__b, __e, __month, __month+24, __ct, __err, false) - __month; if (__i < 24) __m = __i % 12; } @@ -1938,7 +1938,7 @@ ios_base::iostate& __err, const ctype& __ct) const { - int __t = __get_up_to_n_digits(__b, __e, __err, __ct, 2); + int __t = _VSTD::__get_up_to_n_digits(__b, __e, __err, __ct, 2); if (!(__err & ios_base::failbit) && 1 <= __t && __t <= 31) __d = __t; else @@ -2098,7 +2098,7 @@ __err |= ios_base::failbit; return; } - ptrdiff_t __i = __scan_keyword(__b, __e, __ap, __ap+2, __ct, __err, false) - __ap; + ptrdiff_t __i = _VSTD::__scan_keyword(__b, __e, __ap, __ap+2, __ct, __err, false) - __ap; if (__i == 0 && __h == 12) __h = 0; else if (__i == 1 && __h < 12) diff --git a/libcxx/test/std/algorithms/robust_against_adl.pass.cpp b/libcxx/test/std/algorithms/robust_against_adl.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/robust_against_adl.pass.cpp @@ -0,0 +1,183 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03 + +// + +#include +#include + +#include "test_macros.h" + +struct Incomplete; +template struct Holder { T t; }; + +template +struct Intable { + TEST_CONSTEXPR operator int() const { return 1; } +}; + +struct Tester { + using Element = Holder*; + Element data[10]; +}; + +TEST_CONSTEXPR_CXX20 bool test() +{ + Tester t {}; + Tester u {}; + Tester::Element value = nullptr; + Intable count; + + // THESE RELY ON ADL SWAP IN PRACTICE: + // swap_ranges, iter_swap, reverse, rotate, partition + // sort, nth_element + // pop_heap, sort_heap, partial_sort, partial_sort_copy + // next_permutation, prev_permutation + // stable_partition, stable_sort, inplace_merge + // THESE RELY ON ADL SWAP IN THEORY: + // push_heap, make_heap + + (void)std::all_of(t.data, t.data+10, [](void*){ return true; }); + (void)std::any_of(t.data, t.data+10, [](void*){ return true; }); + (void)std::copy(t.data, t.data+10, u.data); + (void)std::copy_n(t.data, count, u.data); + (void)std::copy_backward(t.data, t.data+10, u.data+10); + (void)std::count(t.data, t.data+10, value); + (void)std::count_if(t.data, t.data+10, [](void*){ return true; }); + (void)std::distance(t.data, t.data+10); + (void)std::fill(t.data, t.data+10, value); + (void)std::fill_n(t.data, count, value); + (void)std::find_if(t.data, t.data+10, [](void*){ return true; }); + (void)std::find_if_not(t.data, t.data+10, [](void*){ return true; }); + (void)std::for_each(t.data, t.data+10, [](void*){}); +#if TEST_STD_VER >= 17 + (void)std::for_each_n(t.data, count, [](void*){}); +#endif + (void)std::generate(t.data, t.data+10, [](){ return nullptr; }); + (void)std::generate_n(t.data, count, [](){ return nullptr; }); + (void)std::is_partitioned(t.data, t.data+10, [](void*){ return true; }); + (void)std::move(t.data, t.data+10, u.data); + (void)std::move_backward(t.data, t.data+10, u.data+10); + (void)std::none_of(t.data, t.data+10, [](void*){ return true; }); + (void)std::partition_copy(t.data, t.data+5, u.data, u.data+5, [](void*){ return true; }); + (void)std::partition_point(t.data, t.data+10, [](void*){ return true; }); + (void)std::remove(t.data, t.data+10, value); + (void)std::remove_copy(t.data, t.data+10, u.data, value); + (void)std::remove_copy_if(t.data, t.data+10, u.data, [](void*){ return true; }); + (void)std::remove_if(t.data, t.data+10, [](void*){ return true; }); + (void)std::replace(t.data, t.data+10, value, value); + (void)std::replace_copy(t.data, t.data+10, u.data, value, value); + (void)std::replace_copy_if(t.data, t.data+10, u.data, [](void*){ return true; }, value); + (void)std::replace_if(t.data, t.data+10, [](void*){ return true; }, value); + (void)std::reverse_copy(t.data, t.data+10, u.data); + (void)std::rotate_copy(t.data, t.data+5, t.data+10, u.data); + // TODO: shift_left + // TODO: shift_right + (void)std::transform(t.data, t.data+10, u.data, [](void*){ return nullptr; }); + + // WITHOUT COMPARATORS + (void)std::adjacent_find(t.data, t.data+10); + (void)std::binary_search(t.data, t.data+10, t.data[5]); + (void)std::equal(t.data, t.data+10, u.data); + (void)std::equal_range(t.data, t.data+10, t.data[5]); + (void)std::find_end(t.data, t.data+10, u.data, u.data+5); + (void)std::includes(t.data, t.data+10, u.data, u.data+10); + (void)std::is_heap(t.data, t.data+10); + (void)std::is_heap_until(t.data, t.data+10); + (void)std::is_permutation(t.data, t.data+10, u.data); + (void)std::is_sorted(t.data, t.data+10); + (void)std::is_sorted_until(t.data, t.data+10); + (void)std::lexicographical_compare(t.data, t.data+10, u.data, u.data+10); + // TODO: lexicographical_compare_three_way + (void)std::lower_bound(t.data, t.data+10, t.data[5]); + (void)std::max(value, value); + (void)std::max({ value, value }); + (void)std::max_element(t.data, t.data+10); + (void)std::merge(t.data, t.data+5, t.data+5, t.data+10, u.data); + (void)std::min(value, value); + (void)std::min({ value, value }); + (void)std::min_element(t.data, t.data+10); + (void)std::minmax(value, value); + (void)std::minmax({ value, value }); + (void)std::minmax_element(t.data, t.data+10); + (void)std::mismatch(t.data, t.data+10, u.data); + (void)std::search(t.data, t.data+10, u.data, u.data+5); + (void)std::search_n(t.data, t.data+10, count, value); + (void)std::set_difference(t.data, t.data+5, t.data+5, t.data+10, u.data); + (void)std::set_intersection(t.data, t.data+5, t.data+5, t.data+10, u.data); + (void)std::set_symmetric_difference(t.data, t.data+5, t.data+5, t.data+10, u.data); + (void)std::set_union(t.data, t.data+5, t.data+5, t.data+10, u.data); + (void)std::unique(t.data, t.data+10); + (void)std::unique_copy(t.data, t.data+10, u.data); + (void)std::upper_bound(t.data, t.data+10, t.data[5]); +#if TEST_STD_VER >= 14 + (void)std::equal(t.data, t.data+10, u.data, u.data+10); + (void)std::is_permutation(t.data, t.data+10, u.data, u.data+10); + (void)std::mismatch(t.data, t.data+10, u.data, u.data+10); +#endif +#if TEST_STD_VER >= 20 + (void)std::clamp(value, value, value); +#endif + + // WITH COMPARATORS + (void)std::adjacent_find(t.data, t.data+10, std::equal_to()); + (void)std::binary_search(t.data, t.data+10, value, std::less()); + (void)std::equal(t.data, t.data+10, u.data, std::equal_to()); + (void)std::equal_range(t.data, t.data+10, value, std::less()); + (void)std::find_end(t.data, t.data+10, u.data, u.data+5, std::equal_to()); + (void)std::includes(t.data, t.data+10, u.data, u.data+10, std::less()); + (void)std::is_heap(t.data, t.data+10, std::less()); + (void)std::is_heap_until(t.data, t.data+10, std::less()); + (void)std::is_permutation(t.data, t.data+10, u.data, std::equal_to()); + (void)std::is_sorted(t.data, t.data+10, std::less()); + (void)std::is_sorted_until(t.data, t.data+10, std::less()); + (void)std::lexicographical_compare(t.data, t.data+10, u.data, u.data+10, std::less()); + // TODO: lexicographical_compare_three_way + (void)std::lower_bound(t.data, t.data+10, value, std::less()); + (void)std::max(value, value, std::less()); + (void)std::max({ value, value }, std::less()); + (void)std::max_element(t.data, t.data+10, std::less()); + (void)std::merge(t.data, t.data+5, t.data+5, t.data+10, u.data, std::less()); + (void)std::min(value, value, std::less()); + (void)std::min({ value, value }, std::less()); + (void)std::min_element(t.data, t.data+10, std::less()); + (void)std::minmax(value, value, std::less()); + (void)std::minmax({ value, value }, std::less()); + (void)std::minmax_element(t.data, t.data+10, std::less()); + (void)std::mismatch(t.data, t.data+10, u.data, std::equal_to()); + (void)std::search(t.data, t.data+10, u.data, u.data+5, std::equal_to()); + (void)std::search_n(t.data, t.data+10, count, value, std::equal_to()); + (void)std::set_difference(t.data, t.data+5, t.data+5, t.data+10, u.data, std::less()); + (void)std::set_intersection(t.data, t.data+5, t.data+5, t.data+10, u.data, std::less()); + (void)std::set_symmetric_difference(t.data, t.data+5, t.data+5, t.data+10, u.data, std::less()); + (void)std::set_union(t.data, t.data+5, t.data+5, t.data+10, u.data, std::less()); + (void)std::unique(t.data, t.data+10, std::equal_to()); + (void)std::unique_copy(t.data, t.data+10, u.data, std::equal_to()); + (void)std::upper_bound(t.data, t.data+10, value, std::less()); +#if TEST_STD_VER >= 14 + (void)std::equal(t.data, t.data+10, u.data, u.data+10, std::equal_to()); + (void)std::is_permutation(t.data, t.data+10, u.data, u.data+10, std::equal_to()); + (void)std::mismatch(t.data, t.data+10, u.data, u.data+10, std::equal_to()); +#endif +#if TEST_STD_VER >= 20 + (void)std::clamp(value, value, value, std::less()); +#endif + + return true; +} + +int main(int, char**) +{ + test(); +#if TEST_STD_VER >= 20 + static_assert(test()); +#endif + return 0; +}