code review 5971058: regexp: implement backtracking with pcre fallback

regexp: implement backtracking with pcre fallback

Go's current regular expression package doesn't support all
popular patterns which programmers from other languages have
come to expect.  Notably, the Go regexp package doesn’t
implement the useful backreference functionality.  Without
that, users can't match "catcat" or "dogdog" with (cat|dog)\1
and would need to otherwise fall back to writing multiple
lines of code, possibly involving an "if" statement.

To permit more expressiveness than Go's strictly "regular"
regular expressions, this change permits falling back to the
wildly popular PCRE library when Go would previously return a
compile error.

This permits programmers to copy-paste common regular
expressions from forum sites, stackoverflow, etc. and rest
assured that they'll work as they would have in PHP or Ruby.

Go shouldn't let ideological fundamentalism about algorithmic
purity limit user adoption.

Thanks to Florian Wiemer for his work on the pcre package
which is now promoted to the core library.

This CL doesn't yet implement Perl's (?{ code }) construct. A
future CL will bring Campher into the core, permitting calling
into Perl from Go regular expressions.

Fixes issue 3451

[bradfitz, 2012-04-01 04:01:38]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[mtj1, 2012-04-01 04:07:17]

http://swtch.com/~rsc/regexp/regexp1.html

On Sat, Mar 31, 2012 at 9:01 PM, <bradfitz@golang.org> wrote:

> Reviewers: golang-dev_googlegroups.com,
>
> Message:
> Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),
>
> I'd like you to review this change to
> https://go.googlecode.com/hg/
>
>
> Description:
> regexp: implement backtracking with pcre fallback
>
> Go's current regular expression package doesn't support all
> popular patterns which programmers from other languages have
> come to expect.  Notably, the Go regexp package doesn’t
> implement the useful backreference functionality.  Without
> that, users can't match "catcat" or "dogdog" with (cat|dog)\1
> and would need to otherwise fall back to writing multiple
> lines of code, possibly involving an "if" statement.
>
> To permit more expressiveness than Go's strictly "regular"
> regular expressions, this change permits falling back to the
> wildly popular PCRE library when Go would previously return a
> compile error.
>
> This permits programmers to copy-paste common regular
> expressions from forum sites, stackoverflow, etc. and rest
> assured that they'll work as they would have in PHP or Ruby.
>
> Go shouldn't let ideological fundamentalism about algorithmic
> purity limit user adoption.
>
> Thanks to Florian Wiemer for his work on the pcre package
> which is now promoted to the core library.
>
> This CL doesn't yet implement Perl's (?{ code }) construct. A
> future CL will bring Campher into the core, permitting calling
> into Perl from Go regular expressions.
>
> Fixes issue 3451
>
> Please review this at
http://codereview.appspot.com/**5971058/<http://codereview.appspot.com/5971058/>
>
> Affected files:
>  M src/cmd/api/goapi.go
>  M src/pkg/go/build/deps_test.go
>  M src/pkg/regexp/exec.go
>  A src/pkg/regexp/fallback.go
>  M src/pkg/regexp/find_test.go
>  A src/pkg/regexp/pcre/pcre.go
>  M src/pkg/regexp/regexp.go
>
>
>


-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765

[adg, 2012-04-01 04:07:49]

http://codereview.appspot.com/5971058/diff/1002/src/pkg/regexp/fallback.go
File src/pkg/regexp/fallback.go (right):

http://codereview.appspot.com/5971058/diff/1002/src/pkg/regexp/fallback.go#ne...
src/pkg/regexp/fallback.go:1: // +build !cmd_go_bootstrap
put the build line after the copyright

http://codereview.appspot.com/5971058/diff/3001/src/pkg/regexp/regexp.go
File src/pkg/regexp/regexp.go (right):

http://codereview.appspot.com/5971058/diff/3001/src/pkg/regexp/regexp.go#newc...
src/pkg/regexp/regexp.go:68: var fallbackCompile func(expr string, err error)
(*Regexp, error)
why fallback and not just override? If we're linking in pcre we might as well
use it. it is the industry standard after all

[bradfitz, 2012-04-01 04:11:45]

http://codereview.appspot.com/5971058/diff/1002/src/pkg/regexp/fallback.go
File src/pkg/regexp/fallback.go (right):

http://codereview.appspot.com/5971058/diff/1002/src/pkg/regexp/fallback.go#ne...
src/pkg/regexp/fallback.go:1: // +build !cmd_go_bootstrap
On 2012/04/01 04:07:49, adg wrote:
> put the build line after the copyright

Actually I was bit by this recently, when the copyright was too long.  Russ
admitted it was a bit of a bug and recommended +build lines go before the
copyright.

http://codereview.appspot.com/5971058/diff/3001/src/pkg/regexp/regexp.go
File src/pkg/regexp/regexp.go (right):

http://codereview.appspot.com/5971058/diff/3001/src/pkg/regexp/regexp.go#newc...
src/pkg/regexp/regexp.go:68: var fallbackCompile func(expr string, err error)
(*Regexp, error)
On 2012/04/01 04:07:49, adg wrote:
> why fallback and not just override? If we're linking in pcre we might as well
> use it. it is the industry standard after all

It helps during bootstrapping, when cgo isn't available.  That's about the only
time we need a pure-Go implementation.

[dsymonds, 2012-04-01 04:58:55]

I like the approach, but what about running both native and PCRE in parallel?
There are regular expressions where each is faster, and you could just select
between whichever one finishes first. Go is all about parallel programming,
right?

[bradfitz, 2012-04-01 05:06:03]

Interesting idea.

It could even learn over time (per-*Regexp) which is fastest.
 On Mar 31, 2012 9:58 PM, <dsymonds@golang.org> wrote:

> I like the approach, but what about running both native and PCRE in
> parallel? There are regular expressions where each is faster, and you
> could just select between whichever one finishes first. Go is all about
> parallel programming, right?
>
>
http://codereview.appspot.com/**5971058/<http://codereview.appspot.com/5971058/>
>

[nigeltao, 2012-04-01 05:08:40]

Nice start. Any chance of some benchmarks?

http://codereview.appspot.com/5971058/diff/3001/src/pkg/regexp/fallback.go
File src/pkg/regexp/fallback.go (right):

http://codereview.appspot.com/5971058/diff/3001/src/pkg/regexp/fallback.go#ne...
src/pkg/regexp/fallback.go:51: var buf [4]byte
s/4/utf8.UTFMax/

http://codereview.appspot.com/5971058/diff/3001/src/pkg/regexp/pcre/pcre.go
File src/pkg/regexp/pcre/pcre.go (right):

http://codereview.appspot.com/5971058/diff/3001/src/pkg/regexp/pcre/pcre.go#n...
src/pkg/regexp/pcre/pcre.go:26: // This package provides access to the Perl
Compatible Regular
s/This package/Package pcre/

http://codereview.appspot.com/5971058/diff/3001/src/pkg/regexp/pcre/pcre.go#n...
src/pkg/regexp/pcre/pcre.go:46: // package and the flags defined below, see the
PCRE documentation.
Give a link to the PCRE docs?

http://codereview.appspot.com/5971058/diff/3001/src/pkg/regexp/pcre/pcre.go#n...
src/pkg/regexp/pcre/pcre.go:101: // A reference to a compiled regular
expression.
Regexp is a reference etc.

http://codereview.appspot.com/5971058/diff/3001/src/pkg/regexp/pcre/pcre.go#n...
src/pkg/regexp/pcre/pcre.go:107: // Number of bytes in the compiled pattern
pcresize returns the number of etc.

Similarly with func comments below.

[dsymonds, 2012-04-01 05:09:53]

On Sun, Apr 1, 2012 at 3:06 PM, Brad Fitzpatrick <bradfitz@golang.org> wrote:

> It could even learn over time (per-*Regexp) which is fastest.

A little neural net would train quickly for something like this. We
could SWIG wrap some of the well-studied C++ NN codebases for this
purpose.

[r, 2012-04-01 07:35:40]

LGTM

[0xjnml, 2012-04-01 08:28:05]

On Sunday, April 1, 2012 6:01:38 AM UTC+2, Brad Fitzpatrick wrote:
>
> I'd like you to review this change to 
> https://go.googlecode.com/hg/ 
>
>
> Description: 
> regexp: implement backtracking with pcre fallback 
>

Number on the wall
explained it all ;-)

[zhigangc, 2012-04-23 17:49:50]

We have open-sourced rubex. https://github.com/moovweb/rubex

It uses the same regexp lib (oniguruma) that Ruby uses. 

Please email me if you have questions.

On 2012/04/01 08:28:05, Jan Mercl wrote:
> On Sunday, April 1, 2012 6:01:38 AM UTC+2, Brad Fitzpatrick wrote:
> >
> > I'd like you to review this change to 
> > https://go.googlecode.com/hg/ 
> >
> >
> > Description: 
> > regexp: implement backtracking with pcre fallback 
> >
> 
> Number on the wall
> explained it all ;-)
>

[0xjnml, 2012-04-23 18:14:34]

On 2012/04/23 17:49:50, zhigangc wrote:
> We have open-sourced rubex. https://github.com/moovweb/rubex
> 
> It uses the same regexp lib (oniguruma) that Ruby uses. 

Let me just [re]quote Michael.
On 2012/04/01 04:07:17, mtj1 wrote:
> http://swtch.com/%7Ersc/regexp/regexp1.html