Re: [v3 PATCH] PR libstdc++/78389
On 16/01/17 11:24 +, Jonathan Wakely wrote: OK for trunk with the additional changes to use better magic numbers in the tests. Oh, and for the branches too.
Re: [v3 PATCH] PR libstdc++/78389
On 15/01/17 19:07 +0200, Ville Voutilainen wrote: PR libstdc++/78389 Fix backwards size adjustments. I don't think repeating this text here and ... * include/bits/list.tcc (merge(list&&)): Fix backwards size adjustments. ... here is useful. More useful would be a good Git-style commit log with a separate description on the first line. So the svn commit would have a subject line, followed by a blank line, followed by the content of the ChangeLog entry e.g. PR78389 fix backwards size adjustments PR libstdc++/78389 * include/bits/list.tcc (merge(list&&)): Fix backwards size adjustments. (merge(list&&, _StrictWeakOrdering)): Likewise. * testsuite/23_containers/list/operations/78389.cc: Add better test for the sizes. See the output of "git log --pretty=oneline --abbrev-commit" for why that's useful (and how messy and unhelpful that output is when commits don't have a separate summary on the first line). See also http://chris.beams.io/posts/git-commit/ Anyway ... OK for trunk with the additional changes to use better magic numbers in the tests.
Re: [v3 PATCH] PR libstdc++/78389
On 15 January 2017 at 19:22, Ville Voutilainen
wrote:
> Hmm, and yeah, your test uses a different throw-after number, so I
> should change the tests to do the same. :)
In other words, like in the attached patch.
diff --git a/libstdc++-v3/testsuite/23_containers/list/operations/78389.cc
b/libstdc++-v3/testsuite/23_containers/list/operations/78389.cc
index 3002ba6..4d8b7d2 100644
--- a/libstdc++-v3/testsuite/23_containers/list/operations/78389.cc
+++ b/libstdc++-v3/testsuite/23_containers/list/operations/78389.cc
@@ -57,20 +57,18 @@ int main()
std::list a{1, 2, 3, 4};
std::list b{5, 6, 7, 8, 9, 10, 11, 12};
try {
-a.merge(b, ThrowingComparator{5});
+a.merge(b, ThrowingComparator{4});
} catch (...) {
}
- VERIFY(a.size() == 8 && b.size() == 4);
VERIFY(a.size() == std::distance(a.begin(), a.end()) &&
b.size() == std::distance(b.begin(), b.end()));
std::list ax{1, 2, 3, 4};
std::list bx{5, 6, 7, 8, 9, 10, 11, 12};
- throw_after_X = 5;
+ throw_after_X = 4;
try {
ax.merge(bx);
} catch (...) {
}
- VERIFY(ax.size() == 8 && bx.size() == 4);
VERIFY(ax.size() == std::distance(ax.begin(), ax.end()) &&
bx.size() == std::distance(bx.begin(), bx.end()));
std::list ay{5, 6, 7, 8, 9, 10, 11, 12};
Re: [v3 PATCH] PR libstdc++/78389
On 15 January 2017 at 19:07, Ville Voutilainen wrote: > On 15 January 2017 at 19:01, Ville Voutilainen > wrote: >> On 15 January 2017 at 18:42, Tim Song wrote: >>> On rereading the patch today, the size calculation for merge() appears >>> to be backwards. [__first2, __last2) consists of the nodes not >>> transferred into *this, so the new size of __x should be __dist while >>> this->size() should be incremented by (__orig_size - __dist). >> >> Ah, yes, I'm an idiot. Fixing... > > 2017-01-15 Ville Voutilainen > > PR libstdc++/78389 > Fix backwards size adjustments. > * include/bits/list.tcc (merge(list&&)): > Fix backwards size adjustments. > (merge(list&&, _StrictWeakOrdering)): Likewise. > * testsuite/23_containers/list/operations/78389.cc: Add > better test for the sizes. Hmm, and yeah, your test uses a different throw-after number, so I should change the tests to do the same. :)
Re: [v3 PATCH] PR libstdc++/78389
On 15 January 2017 at 19:01, Ville Voutilainen
wrote:
> On 15 January 2017 at 18:42, Tim Song wrote:
>> On rereading the patch today, the size calculation for merge() appears
>> to be backwards. [__first2, __last2) consists of the nodes not
>> transferred into *this, so the new size of __x should be __dist while
>> this->size() should be incremented by (__orig_size - __dist).
>
> Ah, yes, I'm an idiot. Fixing...
2017-01-15 Ville Voutilainen
PR libstdc++/78389
Fix backwards size adjustments.
* include/bits/list.tcc (merge(list&&)):
Fix backwards size adjustments.
(merge(list&&, _StrictWeakOrdering)): Likewise.
* testsuite/23_containers/list/operations/78389.cc: Add
better test for the sizes.
diff --git a/libstdc++-v3/include/bits/list.tcc
b/libstdc++-v3/include/bits/list.tcc
index 5be49a8..d80d569 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -406,8 +406,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
__catch(...)
{
size_t __dist = std::distance(__first2, __last2);
- this->_M_inc_size(__dist);
- __x._M_set_size(__orig_size - __dist);
+ this->_M_inc_size(__orig_size - __dist);
+ __x._M_set_size(__dist);
__throw_exception_again;
}
}
@@ -454,8 +454,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
__catch(...)
{
size_t __dist = std::distance(__first2, __last2);
- this->_M_inc_size(__dist);
- __x._M_set_size(__orig_size - __dist);
+ this->_M_inc_size(__orig_size - __dist);
+ __x._M_set_size(__dist);
__throw_exception_again;
}
}
diff --git a/libstdc++-v3/testsuite/23_containers/list/operations/78389.cc
b/libstdc++-v3/testsuite/23_containers/list/operations/78389.cc
index 1cf9b0c..3002ba6 100644
--- a/libstdc++-v3/testsuite/23_containers/list/operations/78389.cc
+++ b/libstdc++-v3/testsuite/23_containers/list/operations/78389.cc
@@ -61,6 +61,8 @@ int main()
} catch (...) {
}
VERIFY(a.size() == 8 && b.size() == 4);
+ VERIFY(a.size() == std::distance(a.begin(), a.end()) &&
+b.size() == std::distance(b.begin(), b.end()));
std::list ax{1, 2, 3, 4};
std::list bx{5, 6, 7, 8, 9, 10, 11, 12};
throw_after_X = 5;
@@ -69,6 +71,8 @@ int main()
} catch (...) {
}
VERIFY(ax.size() == 8 && bx.size() == 4);
+ VERIFY(ax.size() == std::distance(ax.begin(), ax.end()) &&
+bx.size() == std::distance(bx.begin(), bx.end()));
std::list ay{5, 6, 7, 8, 9, 10, 11, 12};
try {
ay.sort(ThrowingComparator{5});
Re: [v3 PATCH] PR libstdc++/78389
On 15 January 2017 at 18:42, Tim Song wrote: > On rereading the patch today, the size calculation for merge() appears > to be backwards. [__first2, __last2) consists of the nodes not > transferred into *this, so the new size of __x should be __dist while > this->size() should be incremented by (__orig_size - __dist). Ah, yes, I'm an idiot. Fixing...
Re: [v3 PATCH] PR libstdc++/78389
On Fri, Jan 13, 2017 at 9:26 AM, Ville Voutilainen
wrote:
> Update patch with splices for __carry added. Hopefully this resolves
> the remaining concerns that we had.
On rereading the patch today, the size calculation for merge() appears
to be backwards. [__first2, __last2) consists of the nodes not
transferred into *this, so the new size of __x should be __dist while
this->size() should be incremented by (__orig_size - __dist).
While the original test case in the patch passes (because __dist
happens to be 4 and __orig_size happens to be 8), I see the following
minimally modified test case failing on Wandbox:
std::list a{1, 2, 3, 4};
std::list b{5, 6, 7, 8, 9, 10, 11, 12};
try {
a.merge(b, ThrowingComparator{4});
} catch (...) {
}
assert(a.size() == std::distance(a.begin(), a.end()) && b.size() ==
std::distance(b.begin(), b.end()));
Sorry for not spotting this earlier.
Re: [v3 PATCH] PR libstdc++/78389
On 13/01/17 14:41 +, Jonathan Wakely wrote: On 13/01/17 16:26 +0200, Ville Voutilainen wrote: Update patch with splices for __carry added. Hopefully this resolves the remaining concerns that we had. OK for trunk after fixing the ADL issue noted below. As discussed on IRC, the list::merge() part is a regression compared to gcc4, because we don't store the size in the old list. That part should be backported.
Re: [v3 PATCH] PR libstdc++/78389
On 13/01/17 16:26 +0200, Ville Voutilainen wrote:
Update patch with splices for __carry added. Hopefully this resolves
the remaining concerns that we had.
OK for trunk after fixing the ADL issue noted below.
There are also two stylistic comments ...
diff --git a/libstdc++-v3/include/bits/list.tcc
b/libstdc++-v3/include/bits/list.tcc
index c4f397f..9ba403c 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -380,26 +380,36 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
// 300. list::merge() specification incomplete
if (this != std::__addressof(__x))
{
- _M_check_equal_allocators(__x);
+ _M_check_equal_allocators(__x);
iterator __first1 = begin();
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
- while (__first1 != __last1 && __first2 != __last2)
- if (*__first2 < *__first1)
- {
- iterator __next = __first2;
- _M_transfer(__first1, __first2, ++__next);
- __first2 = __next;
- }
- else
- ++__first1;
- if (__first2 != __last2)
- _M_transfer(__last1, __first2, __last2);
+ size_t __orig_size = __x.size();
This could be const, just to ensure we don't accidentally modify it.
+ __try {
+ while (__first1 != __last1 && __first2 != __last2)
+ if (*__first2 < *__first1)
+ {
+ iterator __next = __first2;
+ _M_transfer(__first1, __first2, ++__next);
+ __first2 = __next;
+ }
+ else
+ ++__first1;
+ if (__first2 != __last2)
+ _M_transfer(__last1, __first2, __last2);
- this->_M_inc_size(__x._M_get_size());
- __x._M_set_size(0);
+ this->_M_inc_size(__x._M_get_size());
+ __x._M_set_size(0);
+ }
+ __catch(...)
+ {
+ size_t __dist = distance(__first2, __last2);
This must be std::distance, so we don't find an overload in a
namespace associated with our value_type or allocator_type.
Same comments for the second merge function as well.
diff --git a/libstdc++-v3/testsuite/23_containers/list/operations/78389.cc
b/libstdc++-v3/testsuite/23_containers/list/operations/78389.cc
new file mode 100644
index 000..fded09d
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/operations/78389.cc
@@ -0,0 +1,85 @@
+// { dg-do run { target c++11 } }
+
+// Copyright (C) 2017 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+//
[v3 PATCH] PR libstdc++/78389
Update patch with splices for __carry added. Hopefully this resolves
the remaining concerns that we had.
diff --git a/libstdc++-v3/include/bits/list.tcc
b/libstdc++-v3/include/bits/list.tcc
index c4f397f..9ba403c 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -380,26 +380,36 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
// 300. list::merge() specification incomplete
if (this != std::__addressof(__x))
{
- _M_check_equal_allocators(__x);
+ _M_check_equal_allocators(__x);
iterator __first1 = begin();
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
- while (__first1 != __last1 && __first2 != __last2)
- if (*__first2 < *__first1)
- {
- iterator __next = __first2;
- _M_transfer(__first1, __first2, ++__next);
- __first2 = __next;
- }
- else
- ++__first1;
- if (__first2 != __last2)
- _M_transfer(__last1, __first2, __last2);
+ size_t __orig_size = __x.size();
+ __try {
+ while (__first1 != __last1 && __first2 != __last2)
+ if (*__first2 < *__first1)
+ {
+ iterator __next = __first2;
+ _M_transfer(__first1, __first2, ++__next);
+ __first2 = __next;
+ }
+ else
+ ++__first1;
+ if (__first2 != __last2)
+ _M_transfer(__last1, __first2, __last2);
- this->_M_inc_size(__x._M_get_size());
- __x._M_set_size(0);
+ this->_M_inc_size(__x._M_get_size());
+ __x._M_set_size(0);
+ }
+ __catch(...)
+ {
+ size_t __dist = distance(__first2, __last2);
+ this->_M_inc_size(__dist);
+ __x._M_set_size(__orig_size - __dist);
+ __throw_exception_again;
+ }
}
}
@@ -423,20 +433,31 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
- while (__first1 != __last1 && __first2 != __last2)
- if (__comp(*__first2, *__first1))
- {
- iterator __next = __first2;
- _M_transfer(__first1, __first2, ++__next);
- __first2 = __next;
- }
- else
- ++__first1;
- if (__first2 != __last2)
- _M_transfer(__last1, __first2, __last2);
-
- this->_M_inc_size(__x._M_get_size());
- __x._M_set_size(0);
+ size_t __orig_size = __x.size();
+ __try
+ {
+ while (__first1 != __last1 && __first2 != __last2)
+ if (__comp(*__first2, *__first1))
+ {
+ iterator __next = __first2;
+ _M_transfer(__first1, __first2, ++__next);
+ __first2 = __next;
+ }
+ else
+ ++__first1;
+ if (__first2 != __last2)
+ _M_transfer(__last1, __first2, __last2);
+
+ this->_M_inc_size(__x._M_get_size());
+ __x._M_set_size(0);
+ }
+ __catch(...)
+ {
+ size_t __dist = distance(__first2, __last2);
+ this->_M_inc_size(__dist);
+ __x._M_set_size(__orig_size - __dist);
+ __throw_exception_again;
+ }
}
}
@@ -453,27 +474,36 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
list __tmp[64];
list * __fill = __tmp;
list * __counter;
-
-do
+ __try
{
- __carry.splice(__carry.begin(), *this, begin());
-
- for(__counter = __tmp;
- __counter != __fill && !__counter->empty();
- ++__counter)
+ do
{
- __counter->merge(__carry);
+ __carry.splice(__carry.begin(), *this, begin());
+
+ for(__counter = __tmp;
+ __counter != __fill && !__counter->empty();
+ ++__counter)
+ {
+ __counter->merge(__carry);
+ __carry.swap(*__counter);
+ }
__carry.swap(*__counter);
+ if (__counter == __fill)
+ ++__fill;
}
- __carry.swap(*__counter);
- if (__counter == __fill)
- ++__fill;
- }
- while ( !empty() );
+ while ( !empty() );
-for (__counter = __tmp + 1; __counter != __fill; ++__counter)
- __counter->merge(*(__counter - 1));
-swap( *(__fill - 1) );
+ for (__counter = __tmp + 1; __counter != __fill; ++__counter)
+ __counter->mer
Re: [v3 PATCH] PR libstdc++/78389
On Fri, Jan 13, 2017 at 3:27 AM, Ville Voutilainen wrote: > On 13 January 2017 at 10:09, Ville Voutilainen > wrote: Ah, I think I see what you're saying. Just splice them back in any order. Ok, I'll give that a spin. >>> >>> Right, list::sort doesn't promise strong exception safety, so >>> "unsorting" is not needed. >>> >>> Also, shouldn't merge() rethrow the caught exception rather than swallow it? >> >> Ha, yes, well spotted. I'll cook up an improved patch. > > Thus: > > 2017-01-13 Ville Voutilainen > > PR libstdc++/78389 > * include/bits/list.tcc (merge(list&&)): > Adjust list sizes if the comparator throws. > (merge(list&&, _StrictWeakOrdering)): Likewise. > (sort()): Splice elements back from the scratch buffers > if the comparator throws. > (sort(_StrictWeakOrdering)): Likewise. > * testsuite/23_containers/list/operations/78389.cc: New. Shouldn't __carry be spliced back as well?
Re: [v3 PATCH] PR libstdc++/78389
On 13 January 2017 at 10:29, Ville Voutilainen wrote: > ..and yes, sigh, that patch has whitespace damage in it. I have > already fixed that, so that'll be corrected before > committing. ..as well as replacing those asserts with VERIFY.
Re: [v3 PATCH] PR libstdc++/78389
On 13 January 2017 at 10:27, Ville Voutilainen wrote: > On 13 January 2017 at 10:09, Ville Voutilainen > wrote: Ah, I think I see what you're saying. Just splice them back in any order. Ok, I'll give that a spin. >>> >>> Right, list::sort doesn't promise strong exception safety, so >>> "unsorting" is not needed. >>> >>> Also, shouldn't merge() rethrow the caught exception rather than swallow it? >> >> Ha, yes, well spotted. I'll cook up an improved patch. > > Thus: > > 2017-01-13 Ville Voutilainen > > PR libstdc++/78389 > * include/bits/list.tcc (merge(list&&)): > Adjust list sizes if the comparator throws. > (merge(list&&, _StrictWeakOrdering)): Likewise. > (sort()): Splice elements back from the scratch buffers > if the comparator throws. > (sort(_StrictWeakOrdering)): Likewise. > * testsuite/23_containers/list/operations/78389.cc: New. ..and yes, sigh, that patch has whitespace damage in it. I have already fixed that, so that'll be corrected before committing.
Re: [v3 PATCH] PR libstdc++/78389
On 13 January 2017 at 10:09, Ville Voutilainen
wrote:
>>> Ah, I think I see what you're saying. Just splice them back in any
>>> order. Ok, I'll give that a spin.
>>
>> Right, list::sort doesn't promise strong exception safety, so
>> "unsorting" is not needed.
>>
>> Also, shouldn't merge() rethrow the caught exception rather than swallow it?
>
> Ha, yes, well spotted. I'll cook up an improved patch.
Thus:
2017-01-13 Ville Voutilainen
PR libstdc++/78389
* include/bits/list.tcc (merge(list&&)):
Adjust list sizes if the comparator throws.
(merge(list&&, _StrictWeakOrdering)): Likewise.
(sort()): Splice elements back from the scratch buffers
if the comparator throws.
(sort(_StrictWeakOrdering)): Likewise.
* testsuite/23_containers/list/operations/78389.cc: New.
diff --git a/libstdc++-v3/include/bits/list.tcc
b/libstdc++-v3/include/bits/list.tcc
index c4f397f..46bb9d2 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -386,20 +386,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
- while (__first1 != __last1 && __first2 != __last2)
- if (*__first2 < *__first1)
- {
- iterator __next = __first2;
- _M_transfer(__first1, __first2, ++__next);
- __first2 = __next;
- }
- else
- ++__first1;
- if (__first2 != __last2)
- _M_transfer(__last1, __first2, __last2);
+ size_t __orig_size = __x.size();
+ __try {
+ while (__first1 != __last1 && __first2 != __last2)
+ if (*__first2 < *__first1)
+ {
+ iterator __next = __first2;
+ _M_transfer(__first1, __first2, ++__next);
+ __first2 = __next;
+ }
+ else
+ ++__first1;
+ if (__first2 != __last2)
+ _M_transfer(__last1, __first2, __last2);
- this->_M_inc_size(__x._M_get_size());
- __x._M_set_size(0);
+ this->_M_inc_size(__x._M_get_size());
+ __x._M_set_size(0);
+ }
+ __catch(...)
+ {
+ size_t __dist = distance(__first2, __last2);
+ this->_M_inc_size(__dist);
+ __x._M_set_size(__orig_size - __dist);
+ __throw_exception_again;
+ }
}
}
@@ -423,20 +433,31 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
- while (__first1 != __last1 && __first2 != __last2)
- if (__comp(*__first2, *__first1))
- {
- iterator __next = __first2;
- _M_transfer(__first1, __first2, ++__next);
- __first2 = __next;
- }
- else
- ++__first1;
- if (__first2 != __last2)
- _M_transfer(__last1, __first2, __last2);
-
- this->_M_inc_size(__x._M_get_size());
- __x._M_set_size(0);
+ size_t __orig_size = __x.size();
+ __try
+ {
+ while (__first1 != __last1 && __first2 != __last2)
+ if (__comp(*__first2, *__first1))
+ {
+ iterator __next = __first2;
+ _M_transfer(__first1, __first2, ++__next);
+ __first2 = __next;
+ }
+ else
+ ++__first1;
+ if (__first2 != __last2)
+ _M_transfer(__last1, __first2, __last2);
+
+ this->_M_inc_size(__x._M_get_size());
+ __x._M_set_size(0);
+ }
+ __catch(...)
+ {
+ size_t __dist = distance(__first2, __last2);
+ this->_M_inc_size(__dist);
+ __x._M_set_size(__orig_size - __dist);
+ __throw_exception_again;
+ }
}
}
@@ -453,27 +474,35 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
list __tmp[64];
list * __fill = __tmp;
list * __counter;
-
-do
+ __try
{
- __carry.splice(__carry.begin(), *this, begin());
-
- for(__counter = __tmp;
- __counter != __fill && !__counter->empty();
- ++__counter)
+ do
{
- __counter->merge(__carry);
+ __carry.splice(__carry.begin(), *this, begin());
+
+ for(__counter = __tmp;
+ __counter != __fill && !__counter->empty();
+ ++__counter)
+ {
+ __counter->merge(__carry);
+ __carry.swap(*__counter);
+ }
__carry.swap(*__counter);
+ if (__cou
Re: [v3 PATCH] PR libstdc++/78389
On 13 January 2017 at 10:02, Tim Song wrote: > On Fri, Jan 13, 2017 at 3:00 AM, Ville Voutilainen > wrote: >> On 13 January 2017 at 09:56, Ville Voutilainen >> wrote: problem with just going through all of them and splicing the contents (if any) back to *this? >>> >>> Well, in addition to the computational complexity of it, not knowing >>> which elements should be spliced >>> back where. If a comparator given to sort() throws, trying to "unsort" >>> with the same comparator >>> can also throw, so I don't know how to reverse the operations done by >>> that point. >> >> Ah, I think I see what you're saying. Just splice them back in any >> order. Ok, I'll give that a spin. > > Right, list::sort doesn't promise strong exception safety, so > "unsorting" is not needed. > > Also, shouldn't merge() rethrow the caught exception rather than swallow it? Ha, yes, well spotted. I'll cook up an improved patch.
Re: [v3 PATCH] PR libstdc++/78389
On Fri, Jan 13, 2017 at 3:00 AM, Ville Voutilainen wrote: > On 13 January 2017 at 09:56, Ville Voutilainen > wrote: >>> problem with just going through all of them and splicing the contents >>> (if any) back to *this? >> >> Well, in addition to the computational complexity of it, not knowing >> which elements should be spliced >> back where. If a comparator given to sort() throws, trying to "unsort" >> with the same comparator >> can also throw, so I don't know how to reverse the operations done by >> that point. > > Ah, I think I see what you're saying. Just splice them back in any > order. Ok, I'll give that a spin. Right, list::sort doesn't promise strong exception safety, so "unsorting" is not needed. Also, shouldn't merge() rethrow the caught exception rather than swallow it?
Re: [v3 PATCH] PR libstdc++/78389
On 13 January 2017 at 09:56, Ville Voutilainen wrote: >> problem with just going through all of them and splicing the contents >> (if any) back to *this? > > Well, in addition to the computational complexity of it, not knowing > which elements should be spliced > back where. If a comparator given to sort() throws, trying to "unsort" > with the same comparator > can also throw, so I don't know how to reverse the operations done by > that point. Ah, I think I see what you're saying. Just splice them back in any order. Ok, I'll give that a spin.
Re: [v3 PATCH] PR libstdc++/78389
On 13 January 2017 at 09:51, Tim Song wrote: >>> Wait, what throwing move? list::sort should be all splicing and no >>> moving, unless I missed something. >> >> It operates based on merge, which moves elements from one list to >> another using a throwing >> comparator. Undoing that operation is fairly tricky, because I don't >> know where the merged >> items landed. Splice is another move operation, but in case of splice, >> I would know where >> the items land, and it also doesn't throw, but merge does. > > But it must be in either the source or the destination, so any missing > elements have to be in one of the 65 temporary lists. Is there a In some positions in one of those temporary lists. I don't know what positions those are. > problem with just going through all of them and splicing the contents > (if any) back to *this? Well, in addition to the computational complexity of it, not knowing which elements should be spliced back where. If a comparator given to sort() throws, trying to "unsort" with the same comparator can also throw, so I don't know how to reverse the operations done by that point.
Re: [v3 PATCH] PR libstdc++/78389
On Fri, Jan 13, 2017 at 1:39 AM, Ville Voutilainen wrote: > On 13 January 2017 at 08:01, Tim Song wrote: >> On Thu, Jan 12, 2017 at 8:11 PM, Ville Voutilainen >> wrote: >>> This patch doesn't try to fix the reported sort() issue, because >>> a) it would require undoing a throwing move operation, which >>> is impossible. >>> b) in order to avoid the throwing move, we would need to add a >>> level of indirection and the scratch space for the indirect data >>> would need to be allocated. >> >> Wait, what throwing move? list::sort should be all splicing and no >> moving, unless I missed something. > > It operates based on merge, which moves elements from one list to > another using a throwing > comparator. Undoing that operation is fairly tricky, because I don't > know where the merged > items landed. Splice is another move operation, but in case of splice, > I would know where > the items land, and it also doesn't throw, but merge does. But it must be in either the source or the destination, so any missing elements have to be in one of the 65 temporary lists. Is there a problem with just going through all of them and splicing the contents (if any) back to *this?
Re: [v3 PATCH] PR libstdc++/78389
On 13 January 2017 at 08:01, Tim Song wrote: > On Thu, Jan 12, 2017 at 8:11 PM, Ville Voutilainen > wrote: >> This patch doesn't try to fix the reported sort() issue, because >> a) it would require undoing a throwing move operation, which >> is impossible. >> b) in order to avoid the throwing move, we would need to add a >> level of indirection and the scratch space for the indirect data >> would need to be allocated. > > Wait, what throwing move? list::sort should be all splicing and no > moving, unless I missed something. It operates based on merge, which moves elements from one list to another using a throwing comparator. Undoing that operation is fairly tricky, because I don't know where the merged items landed. Splice is another move operation, but in case of splice, I would know where the items land, and it also doesn't throw, but merge does.
Re: [v3 PATCH] PR libstdc++/78389
On Thu, Jan 12, 2017 at 8:11 PM, Ville Voutilainen wrote: > This patch doesn't try to fix the reported sort() issue, because > a) it would require undoing a throwing move operation, which > is impossible. > b) in order to avoid the throwing move, we would need to add a > level of indirection and the scratch space for the indirect data > would need to be allocated. Wait, what throwing move? list::sort should be all splicing and no moving, unless I missed something.
[v3 PATCH] PR libstdc++/78389
Tested on Linux-x64.
This patch doesn't try to fix the reported sort() issue, because
a) it would require undoing a throwing move operation, which
is impossible.
b) in order to avoid the throwing move, we would need to add a
level of indirection and the scratch space for the indirect data
would need to be allocated.
2017-01-13 Ville Voutilainen
PR libstdc++/78389
* include/bits/list.tcc (merge(list&&)):
Adjust list sizes if the comparator throws.
(merge(list&&, _StrictWeakOrdering)): Likewise.
* testsuite/23_containers/list/operations/78389.cc: New.
diff --git a/libstdc++-v3/include/bits/list.tcc
b/libstdc++-v3/include/bits/list.tcc
index c4f397f..fabbe7b 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -386,20 +386,29 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
- while (__first1 != __last1 && __first2 != __last2)
- if (*__first2 < *__first1)
- {
- iterator __next = __first2;
- _M_transfer(__first1, __first2, ++__next);
- __first2 = __next;
- }
- else
- ++__first1;
- if (__first2 != __last2)
- _M_transfer(__last1, __first2, __last2);
+ size_t __orig_size = __x.size();
+ __try {
+ while (__first1 != __last1 && __first2 != __last2)
+ if (*__first2 < *__first1)
+ {
+ iterator __next = __first2;
+ _M_transfer(__first1, __first2, ++__next);
+ __first2 = __next;
+ }
+ else
+ ++__first1;
+ if (__first2 != __last2)
+ _M_transfer(__last1, __first2, __last2);
- this->_M_inc_size(__x._M_get_size());
- __x._M_set_size(0);
+ this->_M_inc_size(__x._M_get_size());
+ __x._M_set_size(0);
+ }
+ __catch(...)
+ {
+ size_t __dist = distance(__first2, __last2);
+ this->_M_inc_size(__dist);
+ __x._M_set_size(__orig_size - __dist);
+ }
}
}
@@ -423,20 +432,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
- while (__first1 != __last1 && __first2 != __last2)
- if (__comp(*__first2, *__first1))
- {
- iterator __next = __first2;
- _M_transfer(__first1, __first2, ++__next);
- __first2 = __next;
- }
- else
- ++__first1;
- if (__first2 != __last2)
- _M_transfer(__last1, __first2, __last2);
-
- this->_M_inc_size(__x._M_get_size());
- __x._M_set_size(0);
+ size_t __orig_size = __x.size();
+ __try
+ {
+ while (__first1 != __last1 && __first2 != __last2)
+ if (__comp(*__first2, *__first1))
+ {
+ iterator __next = __first2;
+ _M_transfer(__first1, __first2, ++__next);
+ __first2 = __next;
+ }
+ else
+ ++__first1;
+ if (__first2 != __last2)
+ _M_transfer(__last1, __first2, __last2);
+
+ this->_M_inc_size(__x._M_get_size());
+ __x._M_set_size(0);
+ }
+ __catch(...)
+ {
+ size_t __dist = distance(__first2, __last2);
+ this->_M_inc_size(__dist);
+ __x._M_set_size(__orig_size - __dist);
+ }
}
}
diff --git a/libstdc++-v3/testsuite/23_containers/list/operations/78389.cc
b/libstdc++-v3/testsuite/23_containers/list/operations/78389.cc
new file mode 100644
index 000..3fa9501
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/operations/78389.cc
@@ -0,0 +1,73 @@
+// { dg-do run { target c++11 } }
+
+// Copyright (C) 2017 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+//
