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

[cedstrom@…]

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.

[cedstrom@…]

Overlapping String Test Case

[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

[Marshall Clow]

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

[Marshall Clow]

In [82238] merge fix to release.

[Steven Watanabe]

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.

[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.

[Marshall Clow]

No one complained.

Reverting this.