Bug 192303 - C++11 std::list<>::remove_if() visits elements multiple times
Summary: C++11 std::list<>::remove_if() visits elements multiple times
Status: Closed FIXED
Alias: None
Product: Base System
Classification: Unclassified
Component: bin (show other bugs)
Version: 10.0-STABLE
Hardware: amd64 Any
: --- Affects Many People
Assignee: Dimitry Andric
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-08-01 10:00 UTC by kamikaze
Modified: 2014-08-11 20:38 UTC (History)
4 users (show)

See Also:


Attachments
Bug demo (703 bytes, text/x-c++src)
2014-08-01 10:00 UTC, kamikaze
no flags Details
Proposed fix (496 bytes, patch)
2014-08-02 23:37 UTC, kamikaze
no flags Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description kamikaze 2014-08-01 10:00:11 UTC
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
Comment 1 kamikaze 2014-08-01 10:06:37 UTC
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
Comment 2 kamikaze 2014-08-01 10:52:40 UTC
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/
Comment 3 kamikaze 2014-08-02 23:37:58 UTC
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.
Comment 4 Dimitry Andric freebsd_committer 2014-08-03 19:40:38 UTC
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.
Comment 5 kamikaze 2014-08-04 07:24:43 UTC
I don't see where my patch is incorrect, but yours is definitely more elegant.
Comment 6 kamikaze 2014-08-04 07:40:25 UTC
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.
Comment 7 Dimitry Andric freebsd_committer 2014-08-04 20:30:12 UTC
(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.
Comment 8 kamikaze 2014-08-04 22:27:37 UTC
(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. ;)
Comment 9 commit-hook freebsd_committer 2014-08-08 21:28:18 UTC
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
Comment 10 commit-hook freebsd_committer 2014-08-11 20:37:47 UTC
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
Comment 11 Dimitry Andric freebsd_committer 2014-08-11 20:38:54 UTC
Fixed in head, stable/10 and stable/9.