runtime: Remove now unnecessary pad field from ParFor.

    
    It is not needed due to the removal of the ctx field.
    
    Reviewed-on: https://go-review.googlesource.com/16525


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@229616 138bc75d-0d04-0410-961f-82ee72b054a4

7 files changed, 425 insertions, 19 deletions

diff --git a/libgo/go/regexp/all_test.go b/libgo/go/regexp/all_test.go
index 01ea3742a8b..d78ae6a4cde 100644
--- a/libgo/go/regexp/all_test.go
+++ b/libgo/go/regexp/all_test.go
@@ -489,6 +489,17 @@ func TestOnePassCutoff(t *testing.T) {
 	}
 }
 
+// Check that the same machine can be used with the standard matcher
+// and then the backtracker when there are no captures.
+func TestSwitchBacktrack(t *testing.T) {
+	re := MustCompile(`a|b`)
+	long := make([]byte, maxBacktrackVector+1)
+
+	// The following sequence of Match calls used to panic. See issue #10319.
+	re.Match(long)     // triggers standard matcher
+	re.Match(long[:1]) // triggers backtracker
+}
+
 func BenchmarkLiteral(b *testing.B) {
 	x := strings.Repeat("x", 50) + "y"
 	b.StopTimer()
diff --git a/libgo/go/regexp/backtrack.go b/libgo/go/regexp/backtrack.go
new file mode 100644
index 00000000000..fd95604fe44
--- /dev/null
+++ b/libgo/go/regexp/backtrack.go
@@ -0,0 +1,366 @@
+// Copyright 2015 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.
+
+// backtrack is a regular expression search with submatch
+// tracking for small regular expressions and texts. It allocates
+// a bit vector with (length of input) * (length of prog) bits,
+// to make sure it never explores the same (character position, instruction)
+// state multiple times. This limits the search to run in time linear in
+// the length of the test.
+//
+// backtrack is a fast replacement for the NFA code on small
+// regexps when onepass cannot be used.
+
+package regexp
+
+import "regexp/syntax"
+
+// A job is an entry on the backtracker's job stack. It holds
+// the instruction pc and the position in the input.
+type job struct {
+	pc  uint32
+	arg int
+	pos int
+}
+
+const (
+	visitedBits        = 32
+	maxBacktrackProg   = 500        // len(prog.Inst) <= max
+	maxBacktrackVector = 256 * 1024 // bit vector size <= max (bits)
+)
+
+// bitState holds state for the backtracker.
+type bitState struct {
+	prog *syntax.Prog
+
+	end     int
+	cap     []int
+	input   input
+	jobs    []job
+	visited []uint32
+}
+
+var notBacktrack *bitState = nil
+
+// maxBitStateLen returns the maximum length of a string to search with
+// the backtracker using prog.
+func maxBitStateLen(prog *syntax.Prog) int {
+	if !shouldBacktrack(prog) {
+		return 0
+	}
+	return maxBacktrackVector / len(prog.Inst)
+}
+
+// newBitState returns a new bitState for the given prog,
+// or notBacktrack if the size of the prog exceeds the maximum size that
+// the backtracker will be run for.
+func newBitState(prog *syntax.Prog) *bitState {
+	if !shouldBacktrack(prog) {
+		return notBacktrack
+	}
+	return &bitState{
+		prog: prog,
+	}
+}
+
+// shouldBacktrack reports whether the program is too
+// long for the backtracker to run.
+func shouldBacktrack(prog *syntax.Prog) bool {
+	return len(prog.Inst) <= maxBacktrackProg
+}
+
+// reset resets the state of the backtracker.
+// end is the end position in the input.
+// ncap is the number of captures.
+func (b *bitState) reset(end int, ncap int) {
+	b.end = end
+
+	if cap(b.jobs) == 0 {
+		b.jobs = make([]job, 0, 256)
+	} else {
+		b.jobs = b.jobs[:0]
+	}
+
+	visitedSize := (len(b.prog.Inst)*(end+1) + visitedBits - 1) / visitedBits
+	if cap(b.visited) < visitedSize {
+		b.visited = make([]uint32, visitedSize, maxBacktrackVector/visitedBits)
+	} else {
+		b.visited = b.visited[:visitedSize]
+		for i := range b.visited {
+			b.visited[i] = 0
+		}
+	}
+
+	if cap(b.cap) < ncap {
+		b.cap = make([]int, ncap)
+	} else {
+		b.cap = b.cap[:ncap]
+	}
+	for i := range b.cap {
+		b.cap[i] = -1
+	}
+}
+
+// shouldVisit reports whether the combination of (pc, pos) has not
+// been visited yet.
+func (b *bitState) shouldVisit(pc uint32, pos int) bool {
+	n := uint(int(pc)*(b.end+1) + pos)
+	if b.visited[n/visitedBits]&(1<<(n&(visitedBits-1))) != 0 {
+		return false
+	}
+	b.visited[n/visitedBits] |= 1 << (n & (visitedBits - 1))
+	return true
+}
+
+// push pushes (pc, pos, arg) onto the job stack if it should be
+// visited.
+func (b *bitState) push(pc uint32, pos int, arg int) {
+	if b.prog.Inst[pc].Op == syntax.InstFail {
+		return
+	}
+
+	// Only check shouldVisit when arg == 0.
+	// When arg > 0, we are continuing a previous visit.
+	if arg == 0 && !b.shouldVisit(pc, pos) {
+		return
+	}
+
+	b.jobs = append(b.jobs, job{pc: pc, arg: arg, pos: pos})
+}
+
+// tryBacktrack runs a backtracking search starting at pos.
+func (m *machine) tryBacktrack(b *bitState, i input, pc uint32, pos int) bool {
+	longest := m.re.longest
+	m.matched = false
+
+	b.push(pc, pos, 0)
+	for len(b.jobs) > 0 {
+		l := len(b.jobs) - 1
+		// Pop job off the stack.
+		pc := b.jobs[l].pc
+		pos := b.jobs[l].pos
+		arg := b.jobs[l].arg
+		b.jobs = b.jobs[:l]
+
+		// Optimization: rather than push and pop,
+		// code that is going to Push and continue
+		// the loop simply updates ip, p, and arg
+		// and jumps to CheckAndLoop.  We have to
+		// do the ShouldVisit check that Push
+		// would have, but we avoid the stack
+		// manipulation.
+		goto Skip
+	CheckAndLoop:
+		if !b.shouldVisit(pc, pos) {
+			continue
+		}
+	Skip:
+
+		inst := b.prog.Inst[pc]
+
+		switch inst.Op {
+		default:
+			panic("bad inst")
+		case syntax.InstFail:
+			panic("unexpected InstFail")
+		case syntax.InstAlt:
+			// Cannot just
+			//   b.push(inst.Out, pos, 0)
+			//   b.push(inst.Arg, pos, 0)
+			// If during the processing of inst.Out, we encounter
+			// inst.Arg via another path, we want to process it then.
+			// Pushing it here will inhibit that. Instead, re-push
+			// inst with arg==1 as a reminder to push inst.Arg out
+			// later.
+			switch arg {
+			case 0:
+				b.push(pc, pos, 1)
+				pc = inst.Out
+				goto CheckAndLoop
+			case 1:
+				// Finished inst.Out; try inst.Arg.
+				arg = 0
+				pc = inst.Arg
+				goto CheckAndLoop
+			}
+			panic("bad arg in InstAlt")
+
+		case syntax.InstAltMatch:
+			// One opcode consumes runes; the other leads to match.
+			switch b.prog.Inst[inst.Out].Op {
+			case syntax.InstRune, syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:
+				// inst.Arg is the match.
+				b.push(inst.Arg, pos, 0)
+				pc = inst.Arg
+				pos = b.end
+				goto CheckAndLoop
+			}
+			// inst.Out is the match - non-greedy
+			b.push(inst.Out, b.end, 0)
+			pc = inst.Out
+			goto CheckAndLoop
+
+		case syntax.InstRune:
+			r, width := i.step(pos)
+			if !inst.MatchRune(r) {
+				continue
+			}
+			pos += width
+			pc = inst.Out
+			goto CheckAndLoop
+
+		case syntax.InstRune1:
+			r, width := i.step(pos)
+			if r != inst.Rune[0] {
+				continue
+			}
+			pos += width
+			pc = inst.Out
+			goto CheckAndLoop
+
+		case syntax.InstRuneAnyNotNL:
+			r, width := i.step(pos)
+			if r == '\n' || r == endOfText {
+				continue
+			}
+			pos += width
+			pc = inst.Out
+			goto CheckAndLoop
+
+		case syntax.InstRuneAny:
+			r, width := i.step(pos)
+			if r == endOfText {
+				continue
+			}
+			pos += width
+			pc = inst.Out
+			goto CheckAndLoop
+
+		case syntax.InstCapture:
+			switch arg {
+			case 0:
+				if 0 <= inst.Arg && inst.Arg < uint32(len(b.cap)) {
+					// Capture pos to register, but save old value.
+					b.push(pc, b.cap[inst.Arg], 1) // come back when we're done.
+					b.cap[inst.Arg] = pos
+				}
+				pc = inst.Out
+				goto CheckAndLoop
+			case 1:
+				// Finished inst.Out; restore the old value.
+				b.cap[inst.Arg] = pos
+				continue
+
+			}
+			panic("bad arg in InstCapture")
+			continue
+
+		case syntax.InstEmptyWidth:
+			if syntax.EmptyOp(inst.Arg)&^i.context(pos) != 0 {
+				continue
+			}
+			pc = inst.Out
+			goto CheckAndLoop
+
+		case syntax.InstNop:
+			pc = inst.Out
+			goto CheckAndLoop
+
+		case syntax.InstMatch:
+			// We found a match. If the caller doesn't care
+			// where the match is, no point going further.
+			if len(b.cap) == 0 {
+				m.matched = true
+				return m.matched
+			}
+
+			// Record best match so far.
+			// Only need to check end point, because this entire
+			// call is only considering one start position.
+			if len(b.cap) > 1 {
+				b.cap[1] = pos
+			}
+			if !m.matched || (longest && pos > 0 && pos > m.matchcap[1]) {
+				copy(m.matchcap, b.cap)
+			}
+			m.matched = true
+
+			// If going for first match, we're done.
+			if !longest {
+				return m.matched
+			}
+
+			// If we used the entire text, no longer match is possible.
+			if pos == b.end {
+				return m.matched
+			}
+
+			// Otherwise, continue on in hope of a longer match.
+			continue
+		}
+		panic("unreachable")
+	}
+
+	return m.matched
+}
+
+// backtrack runs a backtracking search of prog on the input starting at pos.
+func (m *machine) backtrack(i input, pos int, end int, ncap int) bool {
+	if !i.canCheckPrefix() {
+		panic("backtrack called for a RuneReader")
+	}
+
+	startCond := m.re.cond
+	if startCond == ^syntax.EmptyOp(0) { // impossible
+		return false
+	}
+	if startCond&syntax.EmptyBeginText != 0 && pos != 0 {
+		// Anchored match, past beginning of text.
+		return false
+	}
+
+	b := m.b
+	b.reset(end, ncap)
+
+	m.matchcap = m.matchcap[:ncap]
+	for i := range m.matchcap {
+		m.matchcap[i] = -1
+	}
+
+	// Anchored search must start at the beginning of the input
+	if startCond&syntax.EmptyBeginText != 0 {
+		if len(b.cap) > 0 {
+			b.cap[0] = pos
+		}
+		return m.tryBacktrack(b, i, uint32(m.p.Start), pos)
+	}
+
+	// Unanchored search, starting from each possible text position.
+	// Notice that we have to try the empty string at the end of
+	// the text, so the loop condition is pos <= end, not pos < end.
+	// This looks like it's quadratic in the size of the text,
+	// but we are not clearing visited between calls to TrySearch,
+	// so no work is duplicated and it ends up still being linear.
+	width := -1
+	for ; pos <= end && width != 0; pos += width {
+		if len(m.re.prefix) > 0 {
+			// Match requires literal prefix; fast search for it.
+			advance := i.index(m.re, pos)
+			if advance < 0 {
+				return false
+			}
+			pos += advance
+		}
+
+		if len(b.cap) > 0 {
+			b.cap[0] = pos
+		}
+		if m.tryBacktrack(b, i, uint32(m.p.Start), pos) {
+			// Match must be leftmost; done.
+			return true
+		}
+		_, width = i.step(pos)
+	}
+	return false
+}
diff --git a/libgo/go/regexp/exec.go b/libgo/go/regexp/exec.go
index c4cb201f642..518272092ae 100644
--- a/libgo/go/regexp/exec.go
+++ b/libgo/go/regexp/exec.go
@@ -35,13 +35,15 @@ type thread struct {
 
 // A machine holds all the state during an NFA simulation for p.
 type machine struct {
-	re       *Regexp      // corresponding Regexp
-	p        *syntax.Prog // compiled program
-	op       *onePassProg // compiled onepass program, or notOnePass
-	q0, q1   queue        // two queues for runq, nextq
-	pool     []*thread    // pool of available threads
-	matched  bool         // whether a match was found
-	matchcap []int        // capture information for the match
+	re             *Regexp      // corresponding Regexp
+	p              *syntax.Prog // compiled program
+	op             *onePassProg // compiled onepass program, or notOnePass
+	maxBitStateLen int          // max length of string to search with bitstate
+	b              *bitState    // state for backtracker, allocated lazily
+	q0, q1         queue        // two queues for runq, nextq
+	pool           []*thread    // pool of available threads
+	matched        bool         // whether a match was found
+	matchcap       []int        // capture information for the match
 
 	// cached inputs, to avoid allocation
 	inputBytes  inputBytes
@@ -76,6 +78,9 @@ func progMachine(p *syntax.Prog, op *onePassProg) *machine {
 	if ncap < 2 {
 		ncap = 2
 	}
+	if op == notOnePass {
+		m.maxBitStateLen = maxBitStateLen(p)
+	}
 	m.matchcap = make([]int, ncap)
 	return m
 }
@@ -422,18 +427,29 @@ var empty = make([]int, 0)
 func (re *Regexp) doExecute(r io.RuneReader, b []byte, s string, pos int, ncap int) []int {
 	m := re.get()
 	var i input
+	var size int
 	if r != nil {
 		i = m.newInputReader(r)
 	} else if b != nil {
 		i = m.newInputBytes(b)
+		size = len(b)
 	} else {
 		i = m.newInputString(s)
+		size = len(s)
 	}
 	if m.op != notOnePass {
 		if !m.onepass(i, pos) {
 			re.put(m)
 			return nil
 		}
+	} else if size < m.maxBitStateLen && r == nil {
+		if m.b == nil {
+			m.b = newBitState(m.p)
+		}
+		if !m.backtrack(i, pos, size, ncap) {
+			re.put(m)
+			return nil
+		}
 	} else {
 		m.init(ncap)
 		if !m.match(i, pos) {
diff --git a/libgo/go/regexp/exec_test.go b/libgo/go/regexp/exec_test.go
index 70d069c0611..4872cb3def4 100644
--- a/libgo/go/regexp/exec_test.go
+++ b/libgo/go/regexp/exec_test.go
@@ -24,8 +24,8 @@ import (
 // complexity, over all possible strings over a given alphabet,
 // up to a given size.  Rather than try to link with RE2, we read a
 // log file containing the test cases and the expected matches.
-// The log file, re2.txt, is generated by running 'make exhaustive-log'
-// in the open source RE2 distribution.  http://code.google.com/p/re2/
+// The log file, re2-exhaustive.txt, is generated by running 'make log'
+// in the open source RE2 distribution https://github.com/google/re2/.
 //
 // The test file format is a sequence of stanzas like:
 //
@@ -59,8 +59,8 @@ import (
 // a capital letter are test names printed during RE2's test suite
 // and are echoed into t but otherwise ignored.
 //
-// At time of writing, re2.txt is 32 MB but compresses to 760 kB,
-// so we store re2.txt.gz in the repository and decompress it on the fly.
+// At time of writing, re2-exhaustive.txt is 59 MB but compresses to 385 kB,
+// so we store re2-exhaustive.txt.bz2 in the repository and decompress it on the fly.
 //
 func TestRE2Search(t *testing.T) {
 	testRE2(t, "testdata/re2-search.txt")
@@ -326,7 +326,7 @@ func same(x, y []int) bool {
 
 // TestFowler runs this package's regexp API against the
 // POSIX regular expression tests collected by Glenn Fowler
-// at http://www2.research.att.com/~gsf/testregex/.
+// at http://www2.research.att.com/~astopen/testregex/testregex.html.
 func TestFowler(t *testing.T) {
 	files, err := filepath.Glob("testdata/*.dat")
 	if err != nil {
@@ -361,7 +361,7 @@ Reading:
 			break Reading
 		}
 
-		// http://www2.research.att.com/~gsf/man/man1/testregex.html
+		// http://www2.research.att.com/~astopen/man/man1/testregex.html
 		//
 		// INPUT FORMAT
 		//   Input lines may be blank, a comment beginning with #, or a test
@@ -713,3 +713,15 @@ func TestLongest(t *testing.T) {
 		t.Errorf("longest match was %q, want %q", g, w)
 	}
 }
+
+// TestProgramTooLongForBacktrack tests that a regex which is too long
+// for the backtracker still executes properly.
+func TestProgramTooLongForBacktrack(t *testing.T) {
+	longRegex := MustCompile(`(one|two|three|four|five|six|seven|eight|nine|ten|eleven|twelve|thirteen|fourteen|fifteen|sixteen|seventeen|eighteen|nineteen|twenty|twentyone|twentytwo|twentythree|twentyfour|twentyfive|twentysix|twentyseven|twentyeight|twentynine|thirty|thirtyone|thirtytwo|thirtythree|thirtyfour|thirtyfive|thirtysix|thirtyseven|thirtyeight|thirtynine|forty|fortyone|fortytwo|fortythree|fortyfour|fortyfive|fortysix|fortyseven|fortyeight|fortynine|fifty|fiftyone|fiftytwo|fiftythree|fiftyfour|fiftyfive|fiftysix|fiftyseven|fiftyeight|fiftynine|sixty|sixtyone|sixtytwo|sixtythree|sixtyfour|sixtyfive|sixtysix|sixtyseven|sixtyeight|sixtynine|seventy|seventyone|seventytwo|seventythree|seventyfour|seventyfive|seventysix|seventyseven|seventyeight|seventynine|eighty|eightyone|eightytwo|eightythree|eightyfour|eightyfive|eightysix|eightyseven|eightyeight|eightynine|ninety|ninetyone|ninetytwo|ninetythree|ninetyfour|ninetyfive|ninetysix|ninetyseven|ninetyeight|ninetynine|onehundred)`)
+	if !longRegex.MatchString("two") {
+		t.Errorf("longRegex.MatchString(\"two\") was false, want true")
+	}
+	if longRegex.MatchString("xxx") {
+		t.Errorf("longRegex.MatchString(\"xxx\") was true, want false")
+	}
+}
diff --git a/libgo/go/regexp/regexp.go b/libgo/go/regexp/regexp.go
index b615acdf0e5..4e4b41242a3 100644
--- a/libgo/go/regexp/regexp.go
+++ b/libgo/go/regexp/regexp.go
@@ -7,9 +7,9 @@
 // The syntax of the regular expressions accepted is the same
 // general syntax used by Perl, Python, and other languages.
 // More precisely, it is the syntax accepted by RE2 and described at
-// http://code.google.com/p/re2/wiki/Syntax, except for \C.
+// https://golang.org/s/re2syntax, except for \C.
 // For an overview of the syntax, run
-//   godoc regexp/syntax
+//   go doc regexp/syntax
 //
 // The regexp implementation provided by this package is
 // guaranteed to run in time linear in the size of the input.
@@ -83,7 +83,7 @@ type Regexp struct {
 	// read-only after Compile
 	expr           string         // as passed to Compile
 	prog           *syntax.Prog   // compiled program
-	onepass        *onePassProg   // onpass program or nil
+	onepass        *onePassProg   // onepass program or nil
 	prefix         string         // required prefix in unanchored matches
 	prefixBytes    []byte         // prefix, as a []byte
 	prefixComplete bool           // prefix is the entire regexp
diff --git a/libgo/go/regexp/syntax/prog.go b/libgo/go/regexp/syntax/prog.go
index 29bd282d0d9..ae6db31a441 100644
--- a/libgo/go/regexp/syntax/prog.go
+++ b/libgo/go/regexp/syntax/prog.go
@@ -189,7 +189,7 @@ Loop:
 
 const noMatch = -1
 
-// MatchRune returns true if the instruction matches (and consumes) r.
+// MatchRune reports whether the instruction matches (and consumes) r.
 // It should only be called when i.Op == InstRune.
 func (i *Inst) MatchRune(r rune) bool {
 	return i.MatchRunePos(r) != noMatch
@@ -256,7 +256,7 @@ func wordRune(r rune) bool {
 		('0' <= r && r <= '9')
 }
 
-// MatchEmptyWidth returns true if the instruction matches
+// MatchEmptyWidth reports whether the instruction matches
 // an empty string between the runes before and after.
 // It should only be called when i.Op == InstEmptyWidth.
 func (i *Inst) MatchEmptyWidth(before rune, after rune) bool {
diff --git a/libgo/go/regexp/testdata/README b/libgo/go/regexp/testdata/README
index b1b301be83f..58cec82f91e 100644
--- a/libgo/go/regexp/testdata/README
+++ b/libgo/go/regexp/testdata/README
@@ -19,5 +19,6 @@ Such changes are marked with 'RE2/Go'.
 RE2 Test Files
 
 re2-exhaustive.txt.bz2 and re2-search.txt are built by running
-'make log' in the RE2 distribution.  http://code.google.com/p/re2/.
+'make log' in the RE2 distribution https://github.com/google/re2/
+
 The exhaustive file is compressed because it is huge.