Re: [Boost-users] Boost Regex Back Reference Issue

Subject: Re: [Boost-users] Boost Regex Back Reference Issue
From: Nick (nospam_at_[hidden])
Date: 2017-07-14 16:26:06

Apologies for replying to my own email.

On Fri, 2017-07-14 at 10:55 -0400, Nick wrote:
> On Thu, 2017-07-13 at 19:20 +0100, John Maddock via Boost-users wrote:
> > > 2.  The other issue is that when I try this example with the string
> > > which is posted to not match, the Boost regex engine runs for a while
> > > and ultimately crashes with a memory error.  (seems like it might be an
> > > endless loop of some sort).  Is that a bug?
> > 
> > Works just fine for me here, if you have a complete self-contained test 
> > case (code, plus compiler version, platform and boost version please) 
> > I'll look into it.
> 
> If it's working for you I'll take a closer look and try to get a small
> repro.  This is happening with GCC 4.9 on Linux (Ubuntu 14 & Gentoo)
> with Boost 1.61.

So I found the cause.  It seems to be caused by the regex pattern and my
code's design.  My pseudo code:

    while boost::regex_search {
        // Store match(es)

        // Move start iterator to end of matches[0]
    }

Well, given the regex:

    ^(a*).*\1$

we've already agreed that this regex is effectively all optional which
means it will match anything, including ^$ (empty string), and I've
confirmed this behavior with Perl.

So the first iteration matches as we'd expect:
    [0] = aaabba, [1] = a

Then all subsequent iterations match on the empty string because the
starting iterator was moved to the end of the first match (which is also
the end of the string) so the reduced regex ^$ matches indefinitely:
    [0] = "", [1] = ""

Since my loop is adding the matches for each iteration, it eventually
hits a bad_alloc exception.

So I guess this is by design for Boost Regex.  Obviously my loop can be
adjusted to bail if start_iterator == end_iterator.  But I wonder if
there's something else my loop should be accounting for?  I suppose
there's nothing that boost::regex_search can do for this situation?

Nick