Boost C++ Libraries: Ticket #9518: string_ref::rfind return value offset

bimaster@… — Thu, 13 Aug 2015 08:37:07 GMT

proposed fix (not fixed yet in 1.59.beta):

size_type rfind(basic_string_ref x, size_t pos = npos) const {
    const_reverse_iterator s = this->crbegin();
    const_reverse_iterator e = this->crend();
    if(pos < size()) s += pos;
    const_reverse_iterator iter = std::search(s, e, x.crbegin(), x.crend(), traits::eq);
    // the only case where substring is searched, reverse_distance not applicable
    return iter == e ? npos : len_ - std::distance(this->crbegin(), iter) - x.size();
}

bibmaster@… — Thu, 13 Aug 2015 09:26:15 GMT

Replying to bimaster@…:

proposed fix (not fixed yet in 1.59.beta):

size_type rfind(basic_string_ref x, size_t pos = npos) const {
    const_reverse_iterator s = this->crbegin();
    const_reverse_iterator e = this->crend();
    if(pos < size()) s += pos;
    const_reverse_iterator iter = std::search(s, e, x.crbegin(), x.crend(), traits::eq);
    // the only case where substring is searched, reverse_distance not applicable
    return iter == e ? npos : len_ - std::distance(this->crbegin(), iter) - x.size();
}

ooops, pos in std::string denotes offset from start, so

if(pos < size()) s += (size() - pos);

bibmaster@… — Thu, 13 Aug 2015 10:24:05 GMT

Replying to bibmaster@…:

ooops, pos in std::string denotes offset from start, so
if(pos < size()) s += (size() - pos);

hmmm, but pos shall be included in search range:

if(pos < size()) s += (size() - pos + 1);

bibmaster@… — Thu, 13 Aug 2015 10:25:39 GMT

if(pos < size()) s += (size() - pos + 1);

error in sign:

if(pos < size()) s += (size() - pos - 1);

bibmaster@… — Thu, 13 Aug 2015 10:45:37 GMT

Replying to bibmaster@…: well, error again: pos is the maximum position where found substring may start:

if(pos < size() && pos + x.size() < size())
    s += (size() - pos - x.size() - 1);

bibmaster@… — Thu, 13 Aug 2015 12:08:23 GMT

Replying to bibmaster@…:

Replying to bibmaster@…: well, error again:

and again...

if(pos < size() && (pos + x.size()) < size())
    s += (size() - (pos + x.size()));

Thu, 13 Aug 2015 13:07:46 GMT

Would you please wait until you have a solution that you're absolutely sure works before posting candidate fixes? Though I'm sure the Boost folks would appreciate a patch (which probably should be submittted through the mailing list or a pull request), I'm getting email on each one of these and it's a bit annoying. Thanks.

Sun, 18 Oct 2015 17:09:06 GMT

In my opinion the proposed fix goes in the wrong direction. The core of the problem lies in the reverse_distance helper, which ought to incorporate a more general length of the string as an offset (currently it is hard-coded to "1", which nicely fits the other usages, but not that in rfind).

I created a PR along with a test case here: https://github.com/boostorg/utility/pull/21

denis.martinez@… — Fri, 05 Aug 2016 14:14:04 GMT

My dev team has hit this bug a few times. It would be really great to have the proposed fix applied, sadly there doesn't seem to be any activity for a bit of time.

This bug remains present in the 1.61.0 release of Boost.

boost::string_ref("abcdefg").rfind("cde") -> 4
std::string("abcdefg").rfind("cde") -> 2

Marshall Clow — Sun, 14 Aug 2016 18:23:08 GMT

Commit 39577f86d1b3a260afc1e7f7caec1ee8f12594bb should fix this.

status changed; resolution set

Marshall Clow — Wed, 17 Aug 2016 20:01:03 GMT

status new → closed
resolution → fixed

Merged to master.