Created attachment 145205 [details] Bug demo When calling std::list<>::remove_if() with a lambda for the condition (I did not test without lambdas), it visits the list entry *following* a delete twice. Attached is a demo of the bug. The number of visits should be 10: # ./main Initial list: 0 1 2 3 4 5 6 7 8 9 Remove odd numbers ... | val | remove |-----|-------- | 0 | | 1 | X | 2 | | 2 | | 3 | X | 4 | | 4 | | 5 | X | 6 | | 6 | | 7 | X | 8 | | 8 | | 9 | X Updated list: 0 2 4 6 8 Visits: 14 Build the test program with: # make CXX="c++ -std=c++11" main
I forgot to post my uname: FreeBSD AprilRyan.norad 10.0-STABLE FreeBSD 10.0-STABLE #0 r268659: Tue Jul 15 11:25:22 CEST 2014 root@AprilRyan.norad:/usr/obj/S403/amd64/usr/src/sys/S403 amd64
Just built it using gcc49: gcc version 4.9.2 20140723 (prerelease) (FreeBSD Ports Collection) It produces the expected output: # ./main Initial list: 0 1 2 3 4 5 6 7 8 9 Remove odd numbers ... | val | remove |-----|-------- | 0 | | 1 | X | 2 | | 3 | X | 4 | | 5 | X | 6 | | 7 | X | 8 | | 9 | X Updated list: 0 2 4 6 8 Visits: 10 I also got independent confirmation of the issue: https://www.bsdforen.de/threads/c-11-bug-unter-freebsd-10.31225/
Created attachment 145275 [details] Proposed fix The issue is an optimisation in the implementation. If __pred(*__i) returns true, the method goes into an inner loop that looks for subsequent items to delete in the list for cumulative deletion. After performing deletion the iterator will point to the first item behind the deleted items. Which has already been visited (returning false ended the inner loop). The proposed patch points the iterator past this list entry - unless the iterator points to the end of the list.
The proposed fix is not correct: when calling erase(i, j), the erased range is up to, but *not* including j. Therefore, j must be incremented before calling erase(), and this will also fix the return value put in i. This issue also applies to std::list<>::remove(). I have posted an updated patch to the upstream bug here: http://llvm.org/PR20520 . If it is accepted upstream, I will commit it into our version of libc++, and MFC it in 3 days.
I don't see where my patch is incorrect, but yours is definitely more elegant.
I just tested your patch. Look at the "updated list" output in the demo. It should read: 0 2 4 6 8 It reads: 0 You erase the element that returned false, too.
(In reply to kamikaze from comment #6) > You erase the element that returned false, too. Yep, my patch was totally wrong, sorry. :-/ Upstream basically did the same patch as you, so thanks! I will commit it soon.
(In reply to Dimitry Andric from comment #7) > (In reply to kamikaze from comment #6) > > You erase the element that returned false, too. > > Yep, my patch was totally wrong, sorry. :-/ We all get days like that. ;)
A commit references this bug: Author: dim Date: Fri Aug 8 21:27:33 UTC 2014 New revision: 269740 URL: http://svnweb.freebsd.org/changeset/base/269740 Log: Pull in r214736 from upstream libc++ trunk (by Marshall Clow): Fix PR#20520 - predicate called too many times in list::remove_if. Add tests for list, forward_list, and the std::remove_if algorithm This fixes an issue where std::list<>::remove_if() and remove() could erroneously visit elements twice. Reported by: Dominic Fandrey <kamikaze@bsdforen.de> PR: 192303 MFC after: 3 days Changes: head/contrib/libc++/include/list
A commit references this bug: Author: dim Date: Mon Aug 11 20:37:04 UTC 2014 New revision: 269836 URL: http://svnweb.freebsd.org/changeset/base/269836 Log: MFC r269740: Pull in r214736 from upstream libc++ trunk (by Marshall Clow): Fix PR#20520 - predicate called too many times in list::remove_if. Add tests for list, forward_list, and the std::remove_if algorithm This fixes an issue where std::list<>::remove_if() and remove() could erroneously visit elements twice. Reported by: Dominic Fandrey <kamikaze@bsdforen.de> PR: 192303 Changes: _U stable/10/ stable/10/contrib/libc++/include/list _U stable/9/contrib/libc++/ stable/9/contrib/libc++/include/list
Fixed in head, stable/10 and stable/9.