123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554 |
- // 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"
- "sync"
- )
- // A queue is a 'sparse array' holding pending threads of execution.
- // See https://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html
- type queue struct {
- sparse []uint32
- dense []entry
- }
- // An 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 https://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
- inputs inputs
- }
- type inputs struct {
- // cached inputs, to avoid allocation
- bytes inputBytes
- string inputString
- reader inputReader
- }
- func (i *inputs) newBytes(b []byte) input {
- i.bytes.str = b
- return &i.bytes
- }
- func (i *inputs) newString(s string) input {
- i.string.str = s
- return &i.string
- }
- func (i *inputs) newReader(r io.RuneReader) input {
- i.reader.r = r
- i.reader.atEOT = false
- i.reader.pos = 0
- return &i.reader
- }
- func (i *inputs) clear() {
- // We need to clear 1 of these.
- // Avoid the expense of clearing the others (pointer write barrier).
- if i.bytes.str != nil {
- i.bytes.str = nil
- } else if i.reader.r != nil {
- i.reader.r = nil
- } else {
- i.string.str = ""
- }
- }
- func (i *inputs) init(r io.RuneReader, b []byte, s string) (input, int) {
- if r != nil {
- return i.newReader(r), 0
- }
- if b != nil {
- return i.newBytes(b), len(b)
- }
- return i.newString(s), len(s)
- }
- 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
- }
- // A lazyFlag is a lazily-evaluated syntax.EmptyOp,
- // for checking zero-width flags like ^ $ \A \z \B \b.
- // It records the pair of relevant runes and does not
- // determine the implied flags until absolutely necessary
- // (most of the time, that means never).
- type lazyFlag uint64
- func newLazyFlag(r1, r2 rune) lazyFlag {
- return lazyFlag(uint64(r1)<<32 | uint64(uint32(r2)))
- }
- func (f lazyFlag) match(op syntax.EmptyOp) bool {
- if op == 0 {
- return true
- }
- r1 := rune(f >> 32)
- if op&syntax.EmptyBeginLine != 0 {
- if r1 != '\n' && r1 >= 0 {
- return false
- }
- op &^= syntax.EmptyBeginLine
- }
- if op&syntax.EmptyBeginText != 0 {
- if r1 >= 0 {
- return false
- }
- op &^= syntax.EmptyBeginText
- }
- if op == 0 {
- return true
- }
- r2 := rune(f)
- if op&syntax.EmptyEndLine != 0 {
- if r2 != '\n' && r2 >= 0 {
- return false
- }
- op &^= syntax.EmptyEndLine
- }
- if op&syntax.EmptyEndText != 0 {
- if r2 >= 0 {
- return false
- }
- op &^= syntax.EmptyEndText
- }
- if op == 0 {
- return true
- }
- if syntax.IsWordChar(r1) != syntax.IsWordChar(r2) {
- op &^= syntax.EmptyWordBoundary
- } else {
- op &^= syntax.EmptyNoWordBoundary
- }
- return op == 0
- }
- // 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 lazyFlag
- if pos == 0 {
- flag = newLazyFlag(-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 = newLazyFlag(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.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 *lazyFlag) {
- 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.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.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.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 *lazyFlag, t *thread) *thread {
- Again:
- 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)
- pc = i.Arg
- goto Again
- case syntax.InstEmptyWidth:
- if cond.match(syntax.EmptyOp(i.Arg)) {
- pc = i.Out
- goto Again
- }
- case syntax.InstNop:
- pc = i.Out
- goto Again
- 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 {
- pc = i.Out
- goto Again
- }
- 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
- }
- type onePassMachine struct {
- inputs inputs
- matchcap []int
- }
- var onePassPool sync.Pool
- func newOnePassMachine() *onePassMachine {
- m, ok := onePassPool.Get().(*onePassMachine)
- if !ok {
- m = new(onePassMachine)
- }
- return m
- }
- func freeOnePassMachine(m *onePassMachine) {
- m.inputs.clear()
- onePassPool.Put(m)
- }
- // doOnePass implements r.doExecute using the one-pass execution engine.
- func (re *Regexp) doOnePass(ir io.RuneReader, ib []byte, is string, pos, ncap int, dstCap []int) []int {
- startCond := re.cond
- if startCond == ^syntax.EmptyOp(0) { // impossible
- return nil
- }
- m := newOnePassMachine()
- if cap(m.matchcap) < ncap {
- m.matchcap = make([]int, ncap)
- } else {
- m.matchcap = m.matchcap[:ncap]
- }
- matched := false
- for i := range m.matchcap {
- m.matchcap[i] = -1
- }
- i, _ := m.inputs.init(ir, ib, is)
- r, r1 := endOfText, endOfText
- width, width1 := 0, 0
- r, width = i.step(pos)
- if r != endOfText {
- r1, width1 = i.step(pos + width)
- }
- var flag lazyFlag
- if pos == 0 {
- flag = newLazyFlag(-1, r)
- } else {
- flag = i.context(pos)
- }
- pc := re.onepass.Start
- inst := re.onepass.Inst[pc]
- // If there is a simple literal prefix, skip over it.
- if pos == 0 && flag.match(syntax.EmptyOp(inst.Arg)) &&
- len(re.prefix) > 0 && i.canCheckPrefix() {
- // Match requires literal prefix; fast search for it.
- if !i.hasPrefix(re) {
- goto Return
- }
- pos += len(re.prefix)
- r, width = i.step(pos)
- r1, width1 = i.step(pos + width)
- flag = i.context(pos)
- pc = int(re.prefixEnd)
- }
- for {
- inst = re.onepass.Inst[pc]
- pc = int(inst.Out)
- switch inst.Op {
- default:
- panic("bad inst")
- case syntax.InstMatch:
- matched = true
- if len(m.matchcap) > 0 {
- m.matchcap[0] = 0
- m.matchcap[1] = pos
- }
- goto Return
- case syntax.InstRune:
- if !inst.MatchRune(r) {
- goto Return
- }
- case syntax.InstRune1:
- if r != inst.Rune[0] {
- goto Return
- }
- case syntax.InstRuneAny:
- // Nothing
- case syntax.InstRuneAnyNotNL:
- if r == '\n' {
- goto Return
- }
- // peek at the input rune to see which branch of the Alt to take
- case syntax.InstAlt, syntax.InstAltMatch:
- pc = int(onePassNext(&inst, r))
- continue
- case syntax.InstFail:
- goto Return
- case syntax.InstNop:
- continue
- case syntax.InstEmptyWidth:
- if !flag.match(syntax.EmptyOp(inst.Arg)) {
- goto Return
- }
- continue
- case syntax.InstCapture:
- if int(inst.Arg) < len(m.matchcap) {
- m.matchcap[inst.Arg] = pos
- }
- continue
- }
- if width == 0 {
- break
- }
- flag = newLazyFlag(r, r1)
- pos += width
- r, width = r1, width1
- if r != endOfText {
- r1, width1 = i.step(pos + width)
- }
- }
- Return:
- if !matched {
- freeOnePassMachine(m)
- return nil
- }
- dstCap = append(dstCap, m.matchcap...)
- freeOnePassMachine(m)
- return dstCap
- }
- // doMatch reports whether either r, b or s match the regexp.
- func (re *Regexp) doMatch(r io.RuneReader, b []byte, s string) bool {
- return re.doExecute(r, b, s, 0, 0, nil) != nil
- }
- // doExecute finds the leftmost match in the input, appends the position
- // of its subexpressions to dstCap and returns dstCap.
- //
- // nil is returned if no matches are found and non-nil if matches are found.
- func (re *Regexp) doExecute(r io.RuneReader, b []byte, s string, pos int, ncap int, dstCap []int) []int {
- if dstCap == nil {
- // Make sure 'return dstCap' is non-nil.
- dstCap = arrayNoInts[:0:0]
- }
- if r == nil && len(b)+len(s) < re.minInputLen {
- return nil
- }
- if re.onepass != nil {
- return re.doOnePass(r, b, s, pos, ncap, dstCap)
- }
- if r == nil && len(b)+len(s) < re.maxBitStateLen {
- return re.backtrack(b, s, pos, ncap, dstCap)
- }
- m := re.get()
- i, _ := m.inputs.init(r, b, s)
- m.init(ncap)
- if !m.match(i, pos) {
- re.put(m)
- return nil
- }
- dstCap = append(dstCap, m.matchcap...)
- re.put(m)
- return dstCap
- }
- // arrayNoInts is returned by doExecute match if nil dstCap is passed
- // to it with ncap=0.
- var arrayNoInts [0]int
|