mclow.lists created this revision.
mclow.lists added reviewers: howard.hinnant, EricWF, rsmith.
mclow.lists added a subscriber: cfe-commits.
libc++'s basic_string class assumes that iterator operations on the iterators
that are passed to it don't throw. This is wrong, and means that we don't meet
the strong exception guarantees in the standard.
A general solution is to do all the work in a temporary string, and then
merge/swap the result into the destination in the end.
However, this is wasteful (extra allocations and copying) when the iterator
operations can't throw.
Here I introduce some scaffolding to support detecting these iterators.
I took an old name from `<algorithm>` that was no longer used:
`__libcpp_is_trivial_iterator` as the basis.
A trivial iterator is a pointer, or one of libc++'s wrapper around another
iterator: `move_iterator`, `reverse_iterator` and `__wrap_iterator` (when the
wrapped iterator is trivial). These are assumed to never throw on indirection,
next/prev, comparison and assignment.
Then I add a string-specific type trait:
`__libcpp_string_gets_noexcept_iterator`, which is either a trivial iterator or
something that has noexcept increment, dereference and comparison. When I get a
non-input iterator where `__libcpp_string_gets_noexcept_iterator<Iter>::value`
is true, I do the algorithm in-place.
Note that this diff is just for `assign`; there are several other cases to deal
with in `<string>`.
I'm looking for feedback on the general direction.
http://reviews.llvm.org/D15862
Files:
include/algorithm
include/iterator
include/string
Index: include/string
===================================================================
--- include/string
+++ include/string
@@ -1201,6 +1201,24 @@
#pragma warning( pop )
#endif // _LIBCPP_MSVC
+#ifdef _LIBCPP_HAS_NO_NOEXCEPT
+struct __libcpp_string_gets_noexcept_iterator_impl : public _LIBCPP_BOOL_CONSTANT(false) {};
+#else
+template <class _Iter>
+struct __libcpp_string_gets_noexcept_iterator_impl : public _LIBCPP_BOOL_CONSTANT((
+ __is_forward_iterator<_Iter>::value &&
+// noexcept(declval<_Iter>().operator++()) &&
+// noexcept(++(declval<_Iter>())) &&
+ noexcept(declval<_Iter>() == declval<_Iter>()) &&
+ noexcept(*declval<_Iter>())
+)) {};
+#endif
+
+
+template <class _Iter>
+struct __libcpp_string_gets_noexcept_iterator
+ : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value || __libcpp_string_gets_noexcept_iterator_impl<_Iter>::value) {};
+
#ifdef _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
template <class _CharT, size_t = sizeof(_CharT)>
@@ -1535,15 +1553,16 @@
template<class _InputIterator>
typename enable_if
<
- __is_input_iterator <_InputIterator>::value &&
- !__is_forward_iterator<_InputIterator>::value,
+ __is_exactly_input_iterator<_InputIterator>::value
+ || !__libcpp_string_gets_noexcept_iterator<_InputIterator>::value,
basic_string&
>::type
assign(_InputIterator __first, _InputIterator __last);
template<class _ForwardIterator>
typename enable_if
<
- __is_forward_iterator<_ForwardIterator>::value,
+ __is_forward_iterator<_ForwardIterator>::value
+ && __libcpp_string_gets_noexcept_iterator<_ForwardIterator>::value,
basic_string&
>::type
assign(_ForwardIterator __first, _ForwardIterator __last);
@@ -2494,15 +2513,15 @@
template<class _InputIterator>
typename enable_if
<
- __is_input_iterator <_InputIterator>::value &&
- !__is_forward_iterator<_InputIterator>::value,
+ __is_exactly_input_iterator <_InputIterator>::value
+ || !__libcpp_string_gets_noexcept_iterator<_InputIterator>::value,
basic_string<_CharT, _Traits, _Allocator>&
>::type
basic_string<_CharT, _Traits, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
{
- clear();
- for (; __first != __last; ++__first)
- push_back(*__first);
+ call_input();
+ basic_string temp(__first, __last);
+ this->swap(temp);
return *this;
}
@@ -2510,11 +2529,13 @@
template<class _ForwardIterator>
typename enable_if
<
- __is_forward_iterator<_ForwardIterator>::value,
+ __is_forward_iterator<_ForwardIterator>::value
+ && __libcpp_string_gets_noexcept_iterator<_ForwardIterator>::value,
basic_string<_CharT, _Traits, _Allocator>&
>::type
basic_string<_CharT, _Traits, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
{
+ call_forward();
size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
size_type __cap = capacity();
if (__cap < __n)
Index: include/iterator
===================================================================
--- include/iterator
+++ include/iterator
@@ -437,6 +437,10 @@
template <class _Tp>
struct __is_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
+template <class _Tp>
+struct __is_exactly_input_iterator
+ : integral_constant<bool, is_same<typename iterator_traits<_Tp>::iterator_category, input_iterator_tag>::value> {};
+
template<class _Category, class _Tp, class _Distance = ptrdiff_t,
class _Pointer = _Tp*, class _Reference = _Tp&>
struct _LIBCPP_TYPE_VIS_ONLY iterator
@@ -1404,6 +1408,23 @@
return __x;
}
+template <class _Iter>
+struct __libcpp_is_trivial_iterator
+ : public _LIBCPP_BOOL_CONSTANT(is_pointer<_Iter>::value) {};
+
+template <class _Iter>
+struct __libcpp_is_trivial_iterator<move_iterator<_Iter> >
+ : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
+
+template <class _Iter>
+struct __libcpp_is_trivial_iterator<reverse_iterator<_Iter> >
+ : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
+
+template <class _Iter>
+struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> >
+ : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
+
+
template <class _Tp, size_t _Np>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
_Tp*
Index: include/algorithm
===================================================================
--- include/algorithm
+++ include/algorithm
@@ -1687,26 +1687,7 @@
}
// copy
-
template <class _Iter>
-struct __libcpp_is_trivial_iterator
-{
- static const bool value = is_pointer<_Iter>::value;
-};
-
-template <class _Iter>
-struct __libcpp_is_trivial_iterator<move_iterator<_Iter> >
-{
- static const bool value = is_pointer<_Iter>::value;
-};
-
-template <class _Iter>
-struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> >
-{
- static const bool value = is_pointer<_Iter>::value;
-};
-
-template <class _Iter>
inline _LIBCPP_INLINE_VISIBILITY
_Iter
__unwrap_iter(_Iter __i)
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
