string_ref::rfind return value offset

[Peter A. Bigot <pab@…>]

The value returned from basic_string_ref::rfind() is calculated based on the where the end of the target string was found, but is not adjusted for the length of that string.

E.g, given

    const char pstr[] = "abcdabc\0abcd";
    string_view sv(pstr, sizeof(pstr)-1);
    const char * pabc = "abc";
    string_view svabc(pabc);

    string_ref::size_type rv = sv.rfind(svabc);

rv will have the value 10 (referencing the last 'c') instead of 8 (referencing the 'a' that starts the match).

[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();
}

[bibmaster@…]

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@…]

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@…]

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

error in sign:

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

[bibmaster@…]

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@…]

Replying to bibmaster@…:

Replying to bibmaster@…: well, error again:

and again...

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

[Peter A. Bigot <pab@…>]

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.

[Alex L. <alxlaus@…>]

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@…]

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]

Commit 39577f86d1b3a260afc1e7f7caec1ee8f12594bb should fix this.

[Marshall Clow]

Merged to master.