code review 5971058: regexp: implement backtracking with pcre fallback

src/pkg/regexp/fallback.go

+// +build !cmd_go_bootstrap

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

put the build line after the copyright

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

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.

+
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package regexp
+
+import (
+        "io"
+        "regexp/pcre"
+        "regexp/syntax"
+        "strings"
+        "unicode/utf8"
+        "unsafe"
+)
+
+func init() {
+        fallbackCompile = func(expr string, err error) (*Regexp, error) {
+                // Try PCRE if Go's regexp package can't handle the pattern.
+                if strings.Contains(expr, `\C`) {
+                        // ... unless it contains \C, because we don't
+                        // care about that and it break tests that
+                        // assume it's broken. Whatever.
+                        return nil, err
+                }
+                pre, perr := pcre.Compile(expr, 0)
+                if perr != nil {
+                        return nil, perr
+                }
+                err = nil
+                r := &Regexp{
+                        expr: expr,
+                        prog: &syntax.Prog{
+                                NumCap: pre.Groups(),
+                        },
+                        numSubexp: pre.Groups(),
+                        fallbackExec: func(r io.RuneReader, b []byte, s string, pos int, ncap int) []int {
+                                return pcreExec(&pre, r, b, s, pos, ncap)
+                        },
+                }
+                return r, nil
+        }
+}
+
+func pcreExec(pre *pcre.Regexp, r io.RuneReader, b []byte, s string, pos int, ncap int) []int {
+        var pm *pcre.Matcher
+        if r != nil {
+                // Inefficient implementation; just repeatedly read a
+                // rune and call pcre Match until we find a match.
+                var buf [4]byte
+                for {
+                        r, _, err := r.ReadRune()
+                        if err != nil {
+                                return nil
+                        }
+                        b = append(b, buf[:utf8.EncodeRune(buf[:], r)]...)
+                        pm = pre.Matcher(b, 0)
+                        if pm.Matches() {
+                                break
+                        }
+                }
+        } else if b != nil {
+                b = b[pos:]
+                pm = pre.Matcher(b, 0)
+        } else {
+                // Allocating here, so pm.Group returns this same byte
+                // slice we can do pointer math on matched groups vs b.
+                b = []byte(s[pos:])
+                pm = pre.Matcher(b, 0)
+        }
+        if !pm.Matches() {
+                return nil
+        }
+        if ncap == 0 {
+                return empty // empty but not nil
+        }
+        cap := make([]int, 0, 2*(ncap+1))
+        for i := 0; i <= ncap; i++ {
+                g := pm.Group(i)
+                off := int(uintptr(unsafe.Pointer(&g[0])) - uintptr(unsafe.Pointer(&b[0])))
+                cap = append(cap, off+pos)
+                cap = append(cap, off+len(g)+pos)
+        }
+        return cap
+}