regexp: hide one-pass code from exported API
Update #8112
Hide one-pass regexp API.
This means moving the code from regexp/syntax to regexp,
but it avoids being locked into the specific API chosen for
the implementation.
It also removes a slice field from the syntax.Inst, which
should avoid bloating the memory footprint of a non-one-pass
regexp unnecessarily.
LGTM=r
R=golang-codereviews, r
CC=golang-codereviews, iant
https://golang.org/cl/98610046
diff --git a/src/pkg/regexp/onepass_test.go b/src/pkg/regexp/onepass_test.go
new file mode 100644
index 0000000..7b2beea
--- /dev/null
+++ b/src/pkg/regexp/onepass_test.go
@@ -0,0 +1,208 @@
+// Copyright 2014 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 (
+ "reflect"
+ "regexp/syntax"
+ "testing"
+)
+
+var runeMergeTests = []struct {
+ left, right, merged []rune
+ next []uint32
+ leftPC, rightPC uint32
+}{
+ {
+ // empty rhs
+ []rune{69, 69},
+ []rune{},
+ []rune{69, 69},
+ []uint32{1},
+ 1, 2,
+ },
+ {
+ // identical runes, identical targets
+ []rune{69, 69},
+ []rune{69, 69},
+ []rune{},
+ []uint32{mergeFailed},
+ 1, 1,
+ },
+ {
+ // identical runes, different targets
+ []rune{69, 69},
+ []rune{69, 69},
+ []rune{},
+ []uint32{mergeFailed},
+ 1, 2,
+ },
+ {
+ // append right-first
+ []rune{69, 69},
+ []rune{71, 71},
+ []rune{69, 69, 71, 71},
+ []uint32{1, 2},
+ 1, 2,
+ },
+ {
+ // append, left-first
+ []rune{71, 71},
+ []rune{69, 69},
+ []rune{69, 69, 71, 71},
+ []uint32{2, 1},
+ 1, 2,
+ },
+ {
+ // successful interleave
+ []rune{60, 60, 71, 71, 101, 101},
+ []rune{69, 69, 88, 88},
+ []rune{60, 60, 69, 69, 71, 71, 88, 88, 101, 101},
+ []uint32{1, 2, 1, 2, 1},
+ 1, 2,
+ },
+ {
+ // left surrounds right
+ []rune{69, 74},
+ []rune{71, 71},
+ []rune{},
+ []uint32{mergeFailed},
+ 1, 2,
+ },
+ {
+ // right surrounds left
+ []rune{69, 74},
+ []rune{68, 75},
+ []rune{},
+ []uint32{mergeFailed},
+ 1, 2,
+ },
+ {
+ // overlap at interval begin
+ []rune{69, 74},
+ []rune{74, 75},
+ []rune{},
+ []uint32{mergeFailed},
+ 1, 2,
+ },
+ {
+ // overlap ar interval end
+ []rune{69, 74},
+ []rune{65, 69},
+ []rune{},
+ []uint32{mergeFailed},
+ 1, 2,
+ },
+ {
+ // overlap from above
+ []rune{69, 74},
+ []rune{71, 74},
+ []rune{},
+ []uint32{mergeFailed},
+ 1, 2,
+ },
+ {
+ // overlap from below
+ []rune{69, 74},
+ []rune{65, 71},
+ []rune{},
+ []uint32{mergeFailed},
+ 1, 2,
+ },
+ {
+ // out of order []rune
+ []rune{69, 74, 60, 65},
+ []rune{66, 67},
+ []rune{},
+ []uint32{mergeFailed},
+ 1, 2,
+ },
+}
+
+func TestMergeRuneSet(t *testing.T) {
+ for ix, test := range runeMergeTests {
+ merged, next := mergeRuneSets(&test.left, &test.right, test.leftPC, test.rightPC)
+ if !reflect.DeepEqual(merged, test.merged) {
+ t.Errorf("mergeRuneSet :%d (%v, %v) merged\n have\n%v\nwant\n%v", ix, test.left, test.right, merged, test.merged)
+ }
+ if !reflect.DeepEqual(next, test.next) {
+ t.Errorf("mergeRuneSet :%d(%v, %v) next\n have\n%v\nwant\n%v", ix, test.left, test.right, next, test.next)
+ }
+ }
+}
+
+const noStr = `!`
+
+var onePass = &onePassProg{}
+
+var onePassTests = []struct {
+ re string
+ onePass *onePassProg
+ prog string
+}{
+ {`^(?:a|(?:a*))$`, notOnePass, noStr},
+ {`^(?:(a)|(?:a*))$`, notOnePass, noStr},
+ {`^(?:(?:(?:.(?:$))?))$`, onePass, `a`},
+ {`^abcd$`, onePass, `abcd`},
+ {`^abcd$`, onePass, `abcde`},
+ {`^(?:(?:a{0,})*?)$`, onePass, `a`},
+ {`^(?:(?:a+)*)$`, onePass, ``},
+ {`^(?:(?:a|(?:aa)))$`, onePass, ``},
+ {`^(?:[^\s\S])$`, onePass, ``},
+ {`^(?:(?:a{3,4}){0,})$`, notOnePass, `aaaaaa`},
+ {`^(?:(?:a+)*)$`, onePass, `a`},
+ {`^(?:(?:(?:a*)+))$`, onePass, noStr},
+ {`^(?:(?:a+)*)$`, onePass, ``},
+ {`^[a-c]+$`, onePass, `abc`},
+ {`^[a-c]*$`, onePass, `abcdabc`},
+ {`^(?:a*)$`, onePass, `aaaaaaa`},
+ {`^(?:(?:aa)|a)$`, onePass, `a`},
+ {`^[a-c]*`, notOnePass, `abcdabc`},
+ {`^[a-c]*$`, onePass, `abc`},
+ {`^...$`, onePass, ``},
+ {`^(?:a|(?:aa))$`, onePass, `a`},
+ {`^[a-c]*`, notOnePass, `abcabc`},
+ {`^a((b))c$`, onePass, noStr},
+ {`^a.[l-nA-Cg-j]?e$`, onePass, noStr},
+ {`^a((b))$`, onePass, noStr},
+ {`^a(?:(b)|(c))c$`, onePass, noStr},
+ {`^a(?:(b*)|(c))c$`, notOnePass, noStr},
+ {`^a(?:b|c)$`, onePass, noStr},
+ {`^a(?:b?|c)$`, onePass, noStr},
+ {`^a(?:b?|c?)$`, notOnePass, noStr},
+ {`^a(?:b?|c+)$`, onePass, noStr},
+ {`^a(?:b+|(bc))d$`, notOnePass, noStr},
+ {`^a(?:bc)+$`, onePass, noStr},
+ {`^a(?:[bcd])+$`, onePass, noStr},
+ {`^a((?:[bcd])+)$`, onePass, noStr},
+ {`^a(:?b|c)*d$`, onePass, `abbbccbbcbbd"`},
+ {`^.bc(d|e)*$`, onePass, `abcddddddeeeededd`},
+ {`^(?:(?:aa)|.)$`, notOnePass, `a`},
+ {`^(?:(?:a{1,2}){1,2})$`, notOnePass, `aaaa`},
+}
+
+func TestCompileOnePass(t *testing.T) {
+ var (
+ p *syntax.Prog
+ re *syntax.Regexp
+ err error
+ )
+ for _, test := range onePassTests {
+ if re, err = syntax.Parse(test.re, syntax.Perl); err != nil {
+ t.Errorf("Parse(%q) got err:%s, want success", test.re, err)
+ continue
+ }
+ // needs to be done before compile...
+ re = re.Simplify()
+ if p, err = syntax.Compile(re); err != nil {
+ t.Errorf("Compile(%q) got err:%s, want success", test.re, err)
+ continue
+ }
+ onePass = compileOnePass(p)
+ if (onePass == notOnePass) != (test.onePass == notOnePass) {
+ t.Errorf("CompileOnePass(%q) got %v, expected %v", test.re, onePass, test.onePass)
+ }
+ }
+}
