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

Attachment: OverlappingStringTest.cpp added

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: Overlapping strings are not properly handled by string::algo::find_all[PATCH] Overlapping strings are not properly handled by string::algo::find_all

comment:3 Changed 5 years ago by Marshall Clow

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

comment:4 Changed 5 years ago by Marshall Clow

Resolution: fixed
Status: newclosed

In [82238] merge fix to release.

comment:5 Changed 5 years ago by Steven Watanabe

Resolution: fixed
Status: closedreopened

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 Clow

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 Clow (previous) (diff)

comment:7 Changed 4 years ago by Marshall Clow

Resolution: invalid
Status: reopenedclosed

No one complained.

Reverting this.

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain Marshall Clow.
The resolution will be deleted.

Add Comment


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

 
Note: See TracTickets for help on using tickets.