src/pkg/regexp/syntax/prog_test.go

// Copyright 2011 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 syntax

import (
	"reflect"
	"testing"
)

var compileTests = []struct {
	Regexp string
	Prog   string
}{
	{"a", `  0	fail
  1*	rune1 "a" -> 2
  2	match
`},
	{"[A-M][n-z]", `  0	fail
  1*	rune "AM" -> 2
  2	rune "nz" -> 3
  3	match
`},
	{"", `  0	fail
  1*	nop -> 2
  2	match
`},
	{"a?", `  0	fail
  1	rune1 "a" -> 3
  2*	alt -> 1, 3
  3	match
`},
	{"a??", `  0	fail
  1	rune1 "a" -> 3
  2*	alt -> 3, 1
  3	match
`},
	{"a+", `  0	fail
  1*	rune1 "a" -> 2
  2	alt -> 1, 3
  3	match
`},
	{"a+?", `  0	fail
  1*	rune1 "a" -> 2
  2	alt -> 3, 1
  3	match
`},
	{"a*", `  0	fail
  1	rune1 "a" -> 2
  2*	alt -> 1, 3
  3	match
`},
	{"a*?", `  0	fail
  1	rune1 "a" -> 2
  2*	alt -> 3, 1
  3	match
`},
	{"a+b+", `  0	fail
  1*	rune1 "a" -> 2
  2	alt -> 1, 3
  3	rune1 "b" -> 4
  4	alt -> 3, 5
  5	match
`},
	{"(a+)(b+)", `  0	fail
  1*	cap 2 -> 2
  2	rune1 "a" -> 3
  3	alt -> 2, 4
  4	cap 3 -> 5
  5	cap 4 -> 6
  6	rune1 "b" -> 7
  7	alt -> 6, 8
  8	cap 5 -> 9
  9	match
`},
	{"a+|b+", `  0	fail
  1	rune1 "a" -> 2
  2	alt -> 1, 6
  3	rune1 "b" -> 4
  4	alt -> 3, 6
  5*	alt -> 1, 3
  6	match
`},
	{"A[Aa]", `  0	fail
  1*	rune1 "A" -> 2
  2	rune "A"/i -> 3
  3	match
`},
	{"(?:(?:^).)", `  0	fail
  1*	empty 4 -> 2
  2	anynotnl -> 3
  3	match
`},
}

func TestCompile(t *testing.T) {
	for _, tt := range compileTests {
		re, _ := Parse(tt.Regexp, Perl)
		p, _ := Compile(re)
		s := p.String()
		if s != tt.Prog {
			t.Errorf("compiled %#q:\n--- have\n%s---\n--- want\n%s---", tt.Regexp, s, tt.Prog)
		}
	}
}

func BenchmarkEmptyOpContext(b *testing.B) {
	for i := 0; i < b.N; i++ {
		var r1 rune = -1
		for _, r2 := range "foo, bar, baz\nsome input text.\n" {
			EmptyOpContext(r1, r2)
			r1 = r2
		}
		EmptyOpContext(r1, -1)
	}
}

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 = &Prog{}

var onePassTests = []struct {
	re      string
	onePass *Prog
	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   *Prog
		re  *Regexp
		err error
	)
	for _, test := range onePassTests {
		if re, err = Parse(test.re, 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 = Compile(re); err != nil {
			t.Errorf("Compile(%q) got err:%s, want success", test.re, err)
			continue
		}
		onePass = p.CompileOnePass()
		if (onePass == NotOnePass) != (test.onePass == NotOnePass) {
			t.Errorf("CompileOnePass(%q) got %v, expected %v", test.re, onePass, test.onePass)
		}
	}
}