Modify

Ticket #7784 (closed Bugs: invalid)

Opened 17 months ago

Last modified 7 months ago

[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

OverlappingStringTest.cpp Download (624 bytes) - added by cedstrom@… 17 months ago.
Overlapping String Test Case

Change History

Changed 17 months ago by cedstrom@…

Overlapping String Test Case

comment:1 Changed 16 months 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 16 months 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 16 months ago by marshall

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

comment:4 Changed 16 months ago by marshall

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

In [82238] merge fix to release.

comment:5 Changed 14 months ago by steven_watanabe

  • Status changed from closed to reopened
  • Resolution fixed deleted

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 8 months 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 7 months ago by marshall (previous) (diff)

comment:7 Changed 7 months ago by marshall

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

No one complained.

Reverting this.

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
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.