[stlport-bugs] [ stlport-Bugs-1872656 ] Edge case: string().find(string())

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 454-5900

Bugs item #1872656, was opened at 2008-01-16 11:30
Message generated for change (Settings changed) made by dums
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=766244&aid=1872656&group_id=146814

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: General code
Group: None
>Status: Open
Resolution: Invalid
Priority: 5
Private: No
Submitted By: howaradr (howaradr)
Assigned to: Petr Ovtchenkov (complement)
Summary: Edge case: string().find(string())

Initial Comment:
See discussion in thread started with https://sourceforge.net/forum/message.php?msg_id=4723253

Summary thereof:

>>> ISO/IEC 14882-2003 extract
21.3.6.1 basic_string::find [lib.string::find] 
size_type find(const basic_string<charT,traits,Allocator>& str, 
size_type pos = 0) const; 
Effects: Determines the lowest position xpos, if possible, such that both of the following conditions 
1 
obtain: 
— pos <= xpos and xpos + str.size() <= size(); 
— at(xpos+I) == str.at(I) for all elements I of the string controlled by str. 
Returns: xpos if the function can determine such a value for xpos. Otherwise, returns npos. 
>>> extract ends

Hence the standard says basic_string::find() returns 0 if str.size()==0 and pos==0.

STLport returns npos in this case.

The relevant code in SVN Trunk version 3388 of stlport\stl\_string.c is below. It is a different overload of find but is used by STLport to implement the overload at issue. It returns npos if this->size()==0, regardless of __n and __pos.

517 template <class _CharT, class _Traits, class _Alloc> __size_type__ 
518 basic_string<_CharT,_Traits,_Alloc> ::find(const _CharT* __s, size_type __pos, 
519 size_type __n) const { 
520 const size_t __len = size(); 
521 if (__pos >= __len || __pos + __n > __len) 
522 return npos;

The following addition to the implementation of void StringTest::find() in test\unit\string_test.cpp would form a test case: 
CPPUNIT_ASSERT( string().find(string())==0 ); 

At present there is no test of this case in SVN Trunk StringTest::find().

----------------------------------------------------------------------

Comment By: Francois Dumont (dums)
Date: 2008-01-17 08:58

Message:
Logged In: YES 
user_id=1096600
Originator: NO

Well, I still have to study the Standard by myself but what I can say for
the moment is that the code you post Petr is not a problem:

if ( p != string::npos ) { // normal 
  char ch = s[p]; // Arghhhhhhhhhh 
}

There is no Arghhhhhh here. You know that string()[0] is valid and returns
the trailing null character. I am even surprise that for the moment
string().at(0) throws and exception, I will check that too.

Whatever, as signal howaradr, this is an edge case. The best would be to
see how other implementations do behave and do the same. We already know
how MSVC implementation behave, we only need to check how GLibC++ behaves
and if they agree do the same. Otherwise we will have to take our own
decision.

----------------------------------------------------------------------

Comment By: Petr Ovtchenkov (complement)
Date: 2008-01-16 22:21

Message:
Logged In: YES 
user_id=615813
Originator: NO

Again,, not a bug. Remain closed.

Reason:

<snip>
21.3.6.1 basic_string::find                      [lib.string::find]
     size_type find(const basic_string<charT,traits,Allocator>& str,
                       size_type pos = 0) const;
Effects: Determines the lowest position xpos, if possible, such that both
of the
following conditions obtain:
 - pos <= xpos and xpos + str.size() <= size();
 - at(xpos+I) == str.at(I) for all elements I of the string controlled by
str.

Returns: xpos if the function can determine such a value for xpos.
Otherwise, returns npos.

Notes: Uses traits::eq().
</snip>

substr() isn't argument: it hasn't chance to return invalid position like
here:

string s; 

string::size_type p = s.find( "", 0, 0 ); 

... 

if ( p != string::npos ) { // normal 
  char ch = s[p]; // Arghhhhhhhhhh 
}

Reference 'like search', not argument, because for search

<snip>
Effects: Finds a subsequence of equal values in a sequence.
Returns: The first iterator i in the range [first1, last1 - (last2 -
first2)) such that for
any non-negative integer n less than last2 - first2 the following
corresponding conditions hold:
   *(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false.
   Returns last1 if no such iterator is found.
</snip>

requirements a bit differ from string's one (return iterator, that may be
end(), not integer).

----------------------------------------------------------------------

Comment By: Ulrich Eckhardt (eckhardt)
Date: 2008-01-16 13:31

Message:
Logged In: YES 
user_id=1522877
Originator: NO

Yes, this is indeed a valid bug.

However, I would go one step further: I'd say the standard says it returns
'pos' if the searched sequence 'str' is empty and 'pos' is a valid index.

Concerning the danger of returning the invalid index 0 from
'string("").find("")', this is just another case that are N+1 places where
you can find the empty string in a string of N elements, e.g. for a
1-element string it can be found at position 0 and 1. Obviously, this
presents a danger, because position 1 is not part of the string, but that
is a problem with the standard and if user actually uses that index, they
are lost anyway. OTOH, if they use 'str.size()' indices starting at the
returned position, this works, because 'str.size()==0'.

Further, look at the definition of e.g. substr(): even there, it requires
'pos <= size()' and _not_ 'pos < size()'. IOW, this behaviour is consistent
throughout the string class.

BTW: Petr, it would have been nice if you had not downright closed the
bugreport only because _you_ disagree. This is just respectless.

Uli

----------------------------------------------------------------------

Comment By: Petr Ovtchenkov (complement)
Date: 2008-01-16 12:10

Message:
Logged In: YES 
user_id=615813
Originator: NO

You ignore "if the function can determine such a value for xpos" of
Standard. 

For size 0 "at(xpos+I) == str.at(I)" can't be accomplished. So I don't see
standard 
fault, and I treat you case as "can't determine such a value".  

string s; 

string::size_type p = s.find( "", 0, 0 ); 

... 

if ( p != string::npos ) { // normal 
  char ch = s[p]; // Arghhhhhhhhhh 
} 

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=766244&aid=1872656&group_id=146814