[Bug libstdc++/61107] New: [4.8/4.9/4.10] stl_algo.h : std::__inplace_stable_partition() doesn't process the whole data range

[tomytsai at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61107

            Bug ID: 61107
           Summary: [4.8/4.9/4.10] stl_algo.h :
                    std::__inplace_stable_partition() doesn't process the
                    whole data range
           Product: gcc
           Version: 4.10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tomytsai at gmail dot com

In GCC 4.8.2 / 4.9 (20140430 snapsot) / 4.10.0 (20140504 snapshot)

If we test the following code:

  auto vec = vector<int> {1, 0, 1}
  auto cmp = [] (int v) {return v == 0;};
  std::__inplace_stable_partition( begin(vec), cmp, vec.size() )

  final vec == {1, 0, 1}
  (the expected result is {0, 1, 1})

It is because of the following line in stl_algo.h :
__inplace_stable_partition()

(from
http://gcc.gnu.org/onlinedocs/gcc-4.9.0/libstdc++/api/a01499_source.html#l01519)

1531  _ForwardIterator __right_split =
1532  std::__find_if_not_n(__middle, __right_len, __pred);
1533  if (__right_len)
1534  __right_split = std::__inplace_stable_partition(__middle,
1535  __pred,
1536  __right_len);

In line 1534, __middle should be replaced with __right_split. Otherwise,
the recursive call will start from __middle, with the updated __right_len
(modified by __find_if_not_n() ), That is, if  __find_if_not_n()  reduces
__right_len , some of the tailing data will leave unprocessed by 
the current function.

Note this problem is not critical because:

1. The corresponding function __stable_partition_adaptive() has the right
   logic (it uses __right_split instead of __middle ). Maybe someone forgot
   to update __inplace_stable_partition() when he/she updated 
   __stable_partition_adaptive().

2. This function is only called when the available buffer size is 0. Otherwise,
   __stable_partition_adaptive() will be called and it has mirrored all the 
   codes from __stable_partition_adaptive(), with the correct logic.

However it is still good to patch this bug. We can do either
   1. Replace the __middle with __right_split , as shown above.
or 2. From stable_partition() , call __stable_partition_adaptive() exclusively.
      This way we can totally remove __inplace_stable_partition(), as 
      __stable_partition_adaptive() is doing the same thing if the memory is 
      not enough (or totally not available).

Thanks!

Tomy