Modify

Opened 5 years ago

Closed 4 years ago

#7784 closed Bugs (invalid)

[PATCH] Overlapping strings are not properly handled by string::algo::find_all

Reported by: cedstrom@… Owned by: marshall
Milestone: To Be Determined Component: string_algo
Version: Boost Development Trunk Severity: Problem
Keywords: Cc:

Description

See attached test case. There should be two matches in the following test case, one at index 0 and one at index 1, but boost::string::algorithm::find_all only finds one at index 0. I suspect the bug is that the string match erroneously restarts from the end of the previous match, not from beginning of the previous match + 1.

Attachments (1)

OverlappingStringTest.cpp (624 bytes) - added by cedstrom@… 5 years ago.
Overlapping String Test Case

Download all attachments as: .zip

Change History (8)

Changed 5 years ago by cedstrom@…

Overlapping String Test Case

comment:1 Changed 5 years ago by anonymous

Patch which I believe fixes this:

Index: boost-trunk/boost/algorithm/string/find_iterator.hpp
===================================================================
--- boost-trunk/boost/algorithm/string/find_iterator.hpp	(revision 82112)
+++ boost-trunk/boost/algorithm/string/find_iterator.hpp	(working copy)
@@ -132,7 +132,10 @@
             // increment
             void increment()
             {
-                m_Match=this->do_find(m_Match.end(),m_End);
+                if(m_Match.begin() == m_Match.end())
+                    m_Match=this->do_find(m_Match.end(),m_End);
+                else
+                    m_Match=this->do_find(m_Match.begin()+1,m_End);
             }
 
             // comparison

comment:2 Changed 5 years ago by anonymous

  • Summary changed from Overlapping strings are not properly handled by string::algo::find_all to [PATCH] Overlapping strings are not properly handled by string::algo::find_all

comment:3 Changed 5 years ago by marshall

Applied patch and added test case in [82117]. Thanks for the patch!

comment:4 Changed 4 years ago by marshall

  • Resolution set to fixed
  • Status changed from new to closed

In [82238] merge fix to release.

comment:5 Changed 4 years ago by steven_watanabe

  • Resolution fixed deleted
  • Status changed from closed to reopened

Marshall, I don't think that this patch should have been applied. I believe that the library is intended to return non-overlapping matches. Rationale: (1) find_all is in split.hpp, the documentation says: "Split algorithms can be used to divide a string into several parts...." (2) For the sake of consistency, find_all, replace_all, and erase_all, should all use the same set of matches. The patch breaks this. (3) boost::regex_iterator also finds non-overlapping matches.

comment:6 Changed 4 years ago by marshall

This fix broke other stuff. See #9063.

I'm considering reverting it.

If you have objections, now would be a good time to speak up.

Last edited 4 years ago by marshall (previous) (diff)

comment:7 Changed 4 years ago by marshall

  • Resolution set to invalid
  • Status changed from reopened to closed

No one complained.

Reverting this.

Add Comment

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain marshall.
The resolution will be deleted. Next status will be 'reopened'.
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.