URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [regexp/] [exec.go] - Blame information for rev 747

Details | Compare with Previous | View Log


// 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 regexp
 
import (
        "io"
        "regexp/syntax"
)
 
// A queue is a 'sparse array' holding pending threads of execution.
// See http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html
type queue struct {
        sparse []uint32
        dense  []entry
}
 
// A entry is an entry on a queue.
// It holds both the instruction pc and the actual thread.
// Some queue entries are just place holders so that the machine
// knows it has considered that pc.  Such entries have t == nil.
type entry struct {
        pc uint32
        t  *thread
}
 
// A thread is the state of a single path through the machine:
// an instruction and a corresponding capture array.
// See http://swtch.com/~rsc/regexp/regexp2.html
type thread struct {
        inst *syntax.Inst
        cap  []int
}
 
// A machine holds all the state during an NFA simulation for p.
type machine struct {
        re       *Regexp      // corresponding Regexp
        p        *syntax.Prog // compiled program
        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
        inputString inputString
        inputReader inputReader
}
 
func (m *machine) newInputBytes(b []byte) input {
        m.inputBytes.str = b
        return &m.inputBytes
}
 
func (m *machine) newInputString(s string) input {
        m.inputString.str = s
        return &m.inputString
}
 
func (m *machine) newInputReader(r io.RuneReader) input {
        m.inputReader.r = r
        m.inputReader.atEOT = false
        m.inputReader.pos = 0
        return &m.inputReader
}
 
// progMachine returns a new machine running the prog p.
func progMachine(p *syntax.Prog) *machine {
        m := &machine{p: p}
        n := len(m.p.Inst)
        m.q0 = queue{make([]uint32, n), make([]entry, 0, n)}
        m.q1 = queue{make([]uint32, n), make([]entry, 0, n)}
        ncap := p.NumCap
        if ncap < 2 {
                ncap = 2
        }
        m.matchcap = make([]int, ncap)
        return m
}
 
func (m *machine) init(ncap int) {
        for _, t := range m.pool {
                t.cap = t.cap[:ncap]
        }
        m.matchcap = m.matchcap[:ncap]
}
 
// alloc allocates a new thread with the given instruction.
// It uses the free pool if possible.
func (m *machine) alloc(i *syntax.Inst) *thread {
        var t *thread
        if n := len(m.pool); n > 0 {
                t = m.pool[n-1]
                m.pool = m.pool[:n-1]
        } else {
                t = new(thread)
                t.cap = make([]int, len(m.matchcap), cap(m.matchcap))
        }
        t.inst = i
        return t
}
 
// free returns t to the free pool.
func (m *machine) free(t *thread) {
        m.inputBytes.str = nil
        m.inputString.str = ""
        m.inputReader.r = nil
        m.pool = append(m.pool, t)
}
 
// match runs the machine over the input starting at pos.
// It reports whether a match was found.
// If so, m.matchcap holds the submatch information.
func (m *machine) match(i input, pos int) bool {
        startCond := m.re.cond
        if startCond == ^syntax.EmptyOp(0) { // impossible
                return false
        }
        m.matched = false
        for i := range m.matchcap {
                m.matchcap[i] = -1
        }
        runq, nextq := &m.q0, &m.q1
        r, r1 := endOfText, endOfText
        width, width1 := 0, 0
        r, width = i.step(pos)
        if r != endOfText {
                r1, width1 = i.step(pos + width)
        }
        var flag syntax.EmptyOp
        if pos == 0 {
                flag = syntax.EmptyOpContext(-1, r)
        } else {
                flag = i.context(pos)
        }
        for {
                if len(runq.dense) == 0 {
                        if startCond&syntax.EmptyBeginText != 0 && pos != 0 {
                                // Anchored match, past beginning of text.
                                break
                        }
                        if m.matched {
                                // Have match; finished exploring alternatives.
                                break
                        }
                        if len(m.re.prefix) > 0 && r1 != m.re.prefixRune && i.canCheckPrefix() {
                                // Match requires literal prefix; fast search for it.
                                advance := i.index(m.re, pos)
                                if advance < 0 {
                                        break
                                }
                                pos += advance
                                r, width = i.step(pos)
                                r1, width1 = i.step(pos + width)
                        }
                }
                if !m.matched {
                        if len(m.matchcap) > 0 {
                                m.matchcap[0] = pos
                        }
                        m.add(runq, uint32(m.p.Start), pos, m.matchcap, flag, nil)
                }
                flag = syntax.EmptyOpContext(r, r1)
                m.step(runq, nextq, pos, pos+width, r, flag)
                if width == 0 {
                        break
                }
                if len(m.matchcap) == 0 && m.matched {
                        // Found a match and not paying attention
                        // to where it is, so any match will do.
                        break
                }
                pos += width
                r, width = r1, width1
                if r != endOfText {
                        r1, width1 = i.step(pos + width)
                }
                runq, nextq = nextq, runq
        }
        m.clear(nextq)
        return m.matched
}
 
// clear frees all threads on the thread queue.
func (m *machine) clear(q *queue) {
        for _, d := range q.dense {
                if d.t != nil {
                        // m.free(d.t)
                        m.pool = append(m.pool, d.t)
                }
        }
        q.dense = q.dense[:0]
}
 
// step executes one step of the machine, running each of the threads
// on runq and appending new threads to nextq.
// The step processes the rune c (which may be endOfText),
// which starts at position pos and ends at nextPos.
// nextCond gives the setting for the empty-width flags after c.
func (m *machine) step(runq, nextq *queue, pos, nextPos int, c rune, nextCond syntax.EmptyOp) {
        longest := m.re.longest
        for j := 0; j < len(runq.dense); j++ {
                d := &runq.dense[j]
                t := d.t
                if t == nil {
                        continue
                }
                if longest && m.matched && len(t.cap) > 0 && m.matchcap[0] < t.cap[0] {
                        // m.free(t)
                        m.pool = append(m.pool, t)
                        continue
                }
                i := t.inst
                add := false
                switch i.Op {
                default:
                        panic("bad inst")
 
                case syntax.InstMatch:
                        if len(t.cap) > 0 && (!longest || !m.matched || m.matchcap[1] < pos) {
                                t.cap[1] = pos
                                copy(m.matchcap, t.cap)
                        }
                        if !longest {
                                // First-match mode: cut off all lower-priority threads.
                                for _, d := range runq.dense[j+1:] {
                                        if d.t != nil {
                                                // m.free(d.t)
                                                m.pool = append(m.pool, d.t)
                                        }
                                }
                                runq.dense = runq.dense[:0]
                        }
                        m.matched = true
 
                case syntax.InstRune:
                        add = i.MatchRune(c)
                case syntax.InstRune1:
                        add = c == i.Rune[0]
                case syntax.InstRuneAny:
                        add = true
                case syntax.InstRuneAnyNotNL:
                        add = c != '\n'
                }
                if add {
                        t = m.add(nextq, i.Out, nextPos, t.cap, nextCond, t)
                }
                if t != nil {
                        // m.free(t)
                        m.pool = append(m.pool, t)
                }
        }
        runq.dense = runq.dense[:0]
}
 
// add adds an entry to q for pc, unless the q already has such an entry.
// It also recursively adds an entry for all instructions reachable from pc by following
// empty-width conditions satisfied by cond.  pos gives the current position
// in the input.
func (m *machine) add(q *queue, pc uint32, pos int, cap []int, cond syntax.EmptyOp, t *thread) *thread {
        if pc == 0 {
                return t
        }
        if j := q.sparse[pc]; j < uint32(len(q.dense)) && q.dense[j].pc == pc {
                return t
        }
 
        j := len(q.dense)
        q.dense = q.dense[:j+1]
        d := &q.dense[j]
        d.t = nil
        d.pc = pc
        q.sparse[pc] = uint32(j)
 
        i := &m.p.Inst[pc]
        switch i.Op {
        default:
                panic("unhandled")
        case syntax.InstFail:
                // nothing
        case syntax.InstAlt, syntax.InstAltMatch:
                t = m.add(q, i.Out, pos, cap, cond, t)
                t = m.add(q, i.Arg, pos, cap, cond, t)
        case syntax.InstEmptyWidth:
                if syntax.EmptyOp(i.Arg)&^cond == 0 {
                        t = m.add(q, i.Out, pos, cap, cond, t)
                }
        case syntax.InstNop:
                t = m.add(q, i.Out, pos, cap, cond, t)
        case syntax.InstCapture:
                if int(i.Arg) < len(cap) {
                        opos := cap[i.Arg]
                        cap[i.Arg] = pos
                        m.add(q, i.Out, pos, cap, cond, nil)
                        cap[i.Arg] = opos
                } else {
                        t = m.add(q, i.Out, pos, cap, cond, t)
                }
        case syntax.InstMatch, syntax.InstRune, syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:
                if t == nil {
                        t = m.alloc(i)
                } else {
                        t.inst = i
                }
                if len(cap) > 0 && &t.cap[0] != &cap[0] {
                        copy(t.cap, cap)
                }
                d.t = t
                t = nil
        }
        return t
}
 
// empty is a non-nil 0-element slice,
// so doExecute can avoid an allocation
// when 0 captures are requested from a successful match.
var empty = make([]int, 0)
 
// doExecute finds the leftmost match in the input and returns
// the position of its subexpressions.
func (re *Regexp) doExecute(r io.RuneReader, b []byte, s string, pos int, ncap int) []int {
        m := re.get()
        var i input
        if r != nil {
                i = m.newInputReader(r)
        } else if b != nil {
                i = m.newInputBytes(b)
        } else {
                i = m.newInputString(s)
        }
        m.init(ncap)
        if !m.match(i, pos) {
                re.put(m)
                return nil
        }
        if ncap == 0 {
                re.put(m)
                return empty // empty but not nil
        }
        cap := make([]int, ncap)
        copy(cap, m.matchcap)
        re.put(m)
        return cap
}

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [regexp/] [exec.go] - Blame information for rev 747

Line No.	Rev	Author	Line
1	747	jeremybenn	`// Copyright 2011 The Go Authors. All rights reserved.`
2			`// Use of this source code is governed by a BSD-style`
3			`// license that can be found in the LICENSE file.`
4
5			`package regexp`
6
7			`import (`
8			`"io"`
9			`"regexp/syntax"`
10			`)`
11
12			`// A queue is a 'sparse array' holding pending threads of execution.`
13			`// See http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html`
14			`type queue struct {`
15			`sparse []uint32`
16			`dense []entry`
17			`}`
18
19			`// A entry is an entry on a queue.`
20			`// It holds both the instruction pc and the actual thread.`
21			`// Some queue entries are just place holders so that the machine`
22			`// knows it has considered that pc. Such entries have t == nil.`
23			`type entry struct {`
24			`pc uint32`
25			`t *thread`
26			`}`
27
28			`// A thread is the state of a single path through the machine:`
29			`// an instruction and a corresponding capture array.`
30			`// See http://swtch.com/~rsc/regexp/regexp2.html`
31			`type thread struct {`
32			`inst *syntax.Inst`
33			`cap []int`
34			`}`
35
36			`// A machine holds all the state during an NFA simulation for p.`
37			`type machine struct {`
38			`re *Regexp // corresponding Regexp`
39			`p *syntax.Prog // compiled program`
40			`q0, q1 queue // two queues for runq, nextq`
41			`pool []*thread // pool of available threads`
42			`matched bool // whether a match was found`
43			`matchcap []int // capture information for the match`
44
45			`// cached inputs, to avoid allocation`
46			`inputBytes inputBytes`
47			`inputString inputString`
48			`inputReader inputReader`
49			`}`
50
51			`func (m *machine) newInputBytes(b []byte) input {`
52			`m.inputBytes.str = b`
53			`return &m.inputBytes`
54			`}`
55
56			`func (m *machine) newInputString(s string) input {`
57			`m.inputString.str = s`
58			`return &m.inputString`
59			`}`
60
61			`func (m *machine) newInputReader(r io.RuneReader) input {`
62			`m.inputReader.r = r`
63			`m.inputReader.atEOT = false`
64			`m.inputReader.pos = 0`
65			`return &m.inputReader`
66			`}`
67
68			`// progMachine returns a new machine running the prog p.`
69			`func progMachine(p syntax.Prog) machine {`
70			`m := &machine{p: p}`
71			`n := len(m.p.Inst)`
72			`m.q0 = queue{make([]uint32, n), make([]entry, 0, n)}`
73			`m.q1 = queue{make([]uint32, n), make([]entry, 0, n)}`
74			`ncap := p.NumCap`
75			`if ncap < 2 {`
76			`ncap = 2`
77			`}`
78			`m.matchcap = make([]int, ncap)`
79			`return m`
80			`}`
81
82			`func (m *machine) init(ncap int) {`
83			`for _, t := range m.pool {`
84			`t.cap = t.cap[:ncap]`
85			`}`
86			`m.matchcap = m.matchcap[:ncap]`
87			`}`
88
89			`// alloc allocates a new thread with the given instruction.`
90			`// It uses the free pool if possible.`
91			`func (m machine) alloc(i syntax.Inst) *thread {`
92			`var t *thread`
93			`if n := len(m.pool); n > 0 {`
94			`t = m.pool[n-1]`
95			`m.pool = m.pool[:n-1]`
96			`} else {`
97			`t = new(thread)`
98			`t.cap = make([]int, len(m.matchcap), cap(m.matchcap))`
99			`}`
100			`t.inst = i`
101			`return t`
102			`}`
103
104			`// free returns t to the free pool.`
105			`func (m machine) free(t thread) {`
106			`m.inputBytes.str = nil`
107			`m.inputString.str = ""`
108			`m.inputReader.r = nil`
109			`m.pool = append(m.pool, t)`
110			`}`
111
112			`// match runs the machine over the input starting at pos.`
113			`// It reports whether a match was found.`
114			`// If so, m.matchcap holds the submatch information.`
115			`func (m *machine) match(i input, pos int) bool {`
116			`startCond := m.re.cond`
117			`if startCond == ^syntax.EmptyOp(0) { // impossible`
118			`return false`
119			`}`
120			`m.matched = false`
121			`for i := range m.matchcap {`
122			`m.matchcap[i] = -1`
123			`}`
124			`runq, nextq := &m.q0, &m.q1`
125			`r, r1 := endOfText, endOfText`
126			`width, width1 := 0, 0`
127			`r, width = i.step(pos)`
128			`if r != endOfText {`
129			`r1, width1 = i.step(pos + width)`
130			`}`
131			`var flag syntax.EmptyOp`
132			`if pos == 0 {`
133			`flag = syntax.EmptyOpContext(-1, r)`
134			`} else {`
135			`flag = i.context(pos)`
136			`}`
137			`for {`
138			`if len(runq.dense) == 0 {`
139			`if startCond&syntax.EmptyBeginText != 0 && pos != 0 {`
140			`// Anchored match, past beginning of text.`
141			`break`
142			`}`
143			`if m.matched {`
144			`// Have match; finished exploring alternatives.`
145			`break`
146			`}`
147			`if len(m.re.prefix) > 0 && r1 != m.re.prefixRune && i.canCheckPrefix() {`
148			`// Match requires literal prefix; fast search for it.`
149			`advance := i.index(m.re, pos)`
150			`if advance < 0 {`
151			`break`
152			`}`
153			`pos += advance`
154			`r, width = i.step(pos)`
155			`r1, width1 = i.step(pos + width)`
156			`}`
157			`}`
158			`if !m.matched {`
159			`if len(m.matchcap) > 0 {`
160			`m.matchcap[0] = pos`
161			`}`
162			`m.add(runq, uint32(m.p.Start), pos, m.matchcap, flag, nil)`
163			`}`
164			`flag = syntax.EmptyOpContext(r, r1)`
165			`m.step(runq, nextq, pos, pos+width, r, flag)`
166			`if width == 0 {`
167			`break`
168			`}`
169			`if len(m.matchcap) == 0 && m.matched {`
170			`// Found a match and not paying attention`
171			`// to where it is, so any match will do.`
172			`break`
173			`}`
174			`pos += width`
175			`r, width = r1, width1`
176			`if r != endOfText {`
177			`r1, width1 = i.step(pos + width)`
178			`}`
179			`runq, nextq = nextq, runq`
180			`}`
181			`m.clear(nextq)`
182			`return m.matched`
183			`}`
184
185			`// clear frees all threads on the thread queue.`
186			`func (m machine) clear(q queue) {`
187			`for _, d := range q.dense {`
188			`if d.t != nil {`
189			`// m.free(d.t)`
190			`m.pool = append(m.pool, d.t)`
191			`}`
192			`}`
193			`q.dense = q.dense[:0]`
194			`}`
195
196			`// step executes one step of the machine, running each of the threads`
197			`// on runq and appending new threads to nextq.`
198			`// The step processes the rune c (which may be endOfText),`
199			`// which starts at position pos and ends at nextPos.`
200			`// nextCond gives the setting for the empty-width flags after c.`
201			`func (m machine) step(runq, nextq queue, pos, nextPos int, c rune, nextCond syntax.EmptyOp) {`
202			`longest := m.re.longest`
203			`for j := 0; j < len(runq.dense); j++ {`
204			`d := &runq.dense[j]`
205			`t := d.t`
206			`if t == nil {`
207			`continue`
208			`}`
209			`if longest && m.matched && len(t.cap) > 0 && m.matchcap[0] < t.cap[0] {`
210			`// m.free(t)`
211			`m.pool = append(m.pool, t)`
212			`continue`
213			`}`
214			`i := t.inst`
215			`add := false`
216			`switch i.Op {`
217			`default:`
218			`panic("bad inst")`
219
220			`case syntax.InstMatch:`
221			`if len(t.cap) > 0 && (!longest \|\| !m.matched \|\| m.matchcap[1] < pos) {`
222			`t.cap[1] = pos`
223			`copy(m.matchcap, t.cap)`
224			`}`
225			`if !longest {`
226			`// First-match mode: cut off all lower-priority threads.`
227			`for _, d := range runq.dense[j+1:] {`
228			`if d.t != nil {`
229			`// m.free(d.t)`
230			`m.pool = append(m.pool, d.t)`
231			`}`
232			`}`
233			`runq.dense = runq.dense[:0]`
234			`}`
235			`m.matched = true`
236
237			`case syntax.InstRune:`
238			`add = i.MatchRune(c)`
239			`case syntax.InstRune1:`
240			`add = c == i.Rune[0]`
241			`case syntax.InstRuneAny:`
242			`add = true`
243			`case syntax.InstRuneAnyNotNL:`
244			`add = c != '\n'`
245			`}`
246			`if add {`
247			`t = m.add(nextq, i.Out, nextPos, t.cap, nextCond, t)`
248			`}`
249			`if t != nil {`
250			`// m.free(t)`
251			`m.pool = append(m.pool, t)`
252			`}`
253			`}`
254			`runq.dense = runq.dense[:0]`
255			`}`
256
257			`// add adds an entry to q for pc, unless the q already has such an entry.`
258			`// It also recursively adds an entry for all instructions reachable from pc by following`
259			`// empty-width conditions satisfied by cond. pos gives the current position`
260			`// in the input.`
261			`func (m machine) add(q queue, pc uint32, pos int, cap []int, cond syntax.EmptyOp, t thread) thread {`
262			`if pc == 0 {`
263			`return t`
264			`}`
265			`if j := q.sparse[pc]; j < uint32(len(q.dense)) && q.dense[j].pc == pc {`
266			`return t`
267			`}`
268
269			`j := len(q.dense)`
270			`q.dense = q.dense[:j+1]`
271			`d := &q.dense[j]`
272			`d.t = nil`
273			`d.pc = pc`
274			`q.sparse[pc] = uint32(j)`
275
276			`i := &m.p.Inst[pc]`
277			`switch i.Op {`
278			`default:`
279			`panic("unhandled")`
280			`case syntax.InstFail:`
281			`// nothing`
282			`case syntax.InstAlt, syntax.InstAltMatch:`
283			`t = m.add(q, i.Out, pos, cap, cond, t)`
284			`t = m.add(q, i.Arg, pos, cap, cond, t)`
285			`case syntax.InstEmptyWidth:`
286			`if syntax.EmptyOp(i.Arg)&^cond == 0 {`
287			`t = m.add(q, i.Out, pos, cap, cond, t)`
288			`}`
289			`case syntax.InstNop:`
290			`t = m.add(q, i.Out, pos, cap, cond, t)`
291			`case syntax.InstCapture:`
292			`if int(i.Arg) < len(cap) {`
293			`opos := cap[i.Arg]`
294			`cap[i.Arg] = pos`
295			`m.add(q, i.Out, pos, cap, cond, nil)`
296			`cap[i.Arg] = opos`
297			`} else {`
298			`t = m.add(q, i.Out, pos, cap, cond, t)`
299			`}`
300			`case syntax.InstMatch, syntax.InstRune, syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:`
301			`if t == nil {`
302			`t = m.alloc(i)`
303			`} else {`
304			`t.inst = i`
305			`}`
306			`if len(cap) > 0 && &t.cap[0] != &cap[0] {`
307			`copy(t.cap, cap)`
308			`}`
309			`d.t = t`
310			`t = nil`
311			`}`
312			`return t`
313			`}`
314
315			`// empty is a non-nil 0-element slice,`
316			`// so doExecute can avoid an allocation`
317			`// when 0 captures are requested from a successful match.`
318			`var empty = make([]int, 0)`
319
320			`// doExecute finds the leftmost match in the input and returns`
321			`// the position of its subexpressions.`
322			`func (re *Regexp) doExecute(r io.RuneReader, b []byte, s string, pos int, ncap int) []int {`
323			`m := re.get()`
324			`var i input`
325			`if r != nil {`
326			`i = m.newInputReader(r)`
327			`} else if b != nil {`
328			`i = m.newInputBytes(b)`
329			`} else {`
330			`i = m.newInputString(s)`
331			`}`
332			`m.init(ncap)`
333			`if !m.match(i, pos) {`
334			`re.put(m)`
335			`return nil`
336			`}`
337			`if ncap == 0 {`
338			`re.put(m)`
339			`return empty // empty but not nil`
340			`}`
341			`cap := make([]int, ncap)`
342			`copy(cap, m.matchcap)`
343			`re.put(m)`
344			`return cap`
345			`}`