From 4a3da3a8a45d5496118798146de1fa4e5798ed5a Mon Sep 17 00:00:00 2001 From: ian Date: Sat, 31 Oct 2015 00:59:47 +0000 Subject: 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 --- libgo/go/regexp/all_test.go | 11 ++ libgo/go/regexp/backtrack.go | 366 ++++++++++++++++++++++++++++++++++++++++ libgo/go/regexp/exec.go | 30 +++- libgo/go/regexp/exec_test.go | 24 ++- libgo/go/regexp/regexp.go | 6 +- libgo/go/regexp/syntax/prog.go | 4 +- libgo/go/regexp/testdata/README | 3 +- 7 files changed, 425 insertions(+), 19 deletions(-) create mode 100644 libgo/go/regexp/backtrack.go (limited to 'libgo/go/regexp') 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. -- cgit v1.2.1