Patch for libstdc++/4354

[Paolo Carlini]

Hi,

I'd like to propose a patch for libstdc++/4354 (a regression from
2.95.x (*)), which follows my analysis included in the PR. I briefly
recall that with the current library the following small program,
proposed
by Roberto Bagnara
---------------------------
#include <iostream>
#include <string>

using namespace std;

int main() {
  string aux = "../BenchCtiTr/apt/mergesort_ap_variant.pl";
  string::size_type i = aux.rfind("/");
  if (i != string::npos)
    aux.assign(aux, i+1, string::npos);

  cout << aux.c_str() << endl;
  cout << aux << endl;
}
----------------------------
outputs:
merge
mergeort_ap_variant.pl

instead of the expected:
mergesort_ap_variant.pl
mergesort_ap_variant.pl

After some lenghty debugging sessions I traced back the problem to the
following function in basic_string.tcc:

  template<typename _CharT, typename _Traits, typename _Alloc>
    template<typename _ForwardIter>
      basic_string<_CharT, _Traits, _Alloc>&
      basic_string<_CharT, _Traits, _Alloc>::
      _M_replace(iterator __i1, iterator __i2, _ForwardIter __k1,
                 _ForwardIter __k2, forward_iterator_tag)
      {
        size_type __dold = __i2 - __i1;
        size_type __dmax = this->max_size();
        size_type __dnew = static_cast<size_type>(distance(__k1, __k2));

        if (__dmax <= __dnew)
          __throw_length_error("basic_string::_M_replace");
        size_type __off = __i1 - _M_ibegin();
        _M_mutate(__off, __dold, __dnew);
        // Invalidated __i1, __i2
        if (__dnew)
          _S_copy_chars(_M_data() + __off, __k1, __k2);

        return *this;
      }

Clearly, when source and destination strings are the very
same string, _M_mutate clobbers the internal string data before the
actual
_S_copy_chars occurs (in the test program, __dnew= 23 and __dold = 41):

So (in close analogy with what done by other reference implementations)
I
propose to radically solve the problem by simply exchanging _M_mutate
and
_S_copy_chars calls every time __dnew < __dold and therefore there is no
reason
at all to call _M_mutate before _S_copy_chars.

I strongly believe that the patch is correct and indeed I checked that
Roberto's
testcase (and variants of it) now runs fine and that there are no
regressions in
testsuite (regression checking revealed a small error in a previous
version
whereas I did'nt call at all _M_mutate when __dnew == __dold). However,
the code could be perhaps optimized (loosing a bit of clarity) by
avoiding the
check of some of the three if conditions for specific execution paths.

Please thoroughly test the patch and apply it if ok.

Cheers,
Paolo Carlini.

(*) Three other independent implementations confirmed the regression in
addition
to my own ;-) interpretation of the ISO standard.



Index: gcc/libstdc++-v3/include/bits/basic_string.tcc
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/basic_string.tcc,v
retrieving revision 1.6
diff -c -3 -p -r1.6 basic_string.tcc
*** basic_string.tcc    2001/07/20 00:09:31     1.6
--- basic_string.tcc    2001/09/21 22:35:59
*************** namespace std
*** 453,462 ****
        if (__dmax <= __dnew)
          __throw_length_error("basic_string::_M_replace");
        size_type __off = __i1 - _M_ibegin();
!       _M_mutate(__off, __dold, __dnew);
!       // Invalidated __i1, __i2
        if (__dnew)
          _S_copy_chars(_M_data() + __off, __k1, __k2);

        return *this;
        }
--- 453,464 ----
        if (__dmax <= __dnew)
          __throw_length_error("basic_string::_M_replace");
        size_type __off = __i1 - _M_ibegin();
!       if (__dnew >= __dold)
!         _M_mutate(__off, __dold, __dnew);  // Invalidated __i1, __i2
        if (__dnew)
          _S_copy_chars(_M_data() + __off, __k1, __k2);
+       if (__dnew < __dold)
+         _M_mutate(__off, __dold, __dnew);

        return *this;
        }