Source file src/pkg/regexp/exec.go

     1	// 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		"sync"
    11	)
    12	
    13	// A queue is a 'sparse array' holding pending threads of execution.
    14	// See https://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html
    15	type queue struct {
    16		sparse []uint32
    17		dense  []entry
    18	}
    19	
    20	// An entry is an entry on a queue.
    21	// It holds both the instruction pc and the actual thread.
    22	// Some queue entries are just place holders so that the machine
    23	// knows it has considered that pc. Such entries have t == nil.
    24	type entry struct {
    25		pc uint32
    26		t  *thread
    27	}
    28	
    29	// A thread is the state of a single path through the machine:
    30	// an instruction and a corresponding capture array.
    31	// See https://swtch.com/~rsc/regexp/regexp2.html
    32	type thread struct {
    33		inst *syntax.Inst
    34		cap  []int
    35	}
    36	
    37	// A machine holds all the state during an NFA simulation for p.
    38	type machine struct {
    39		re       *Regexp      // corresponding Regexp
    40		p        *syntax.Prog // compiled program
    41		q0, q1   queue        // two queues for runq, nextq
    42		pool     []*thread    // pool of available threads
    43		matched  bool         // whether a match was found
    44		matchcap []int        // capture information for the match
    45	
    46		inputs inputs
    47	}
    48	
    49	type inputs struct {
    50		// cached inputs, to avoid allocation
    51		bytes  inputBytes
    52		string inputString
    53		reader inputReader
    54	}
    55	
    56	func (i *inputs) newBytes(b []byte) input {
    57		i.bytes.str = b
    58		return &i.bytes
    59	}
    60	
    61	func (i *inputs) newString(s string) input {
    62		i.string.str = s
    63		return &i.string
    64	}
    65	
    66	func (i *inputs) newReader(r io.RuneReader) input {
    67		i.reader.r = r
    68		i.reader.atEOT = false
    69		i.reader.pos = 0
    70		return &i.reader
    71	}
    72	
    73	func (i *inputs) clear() {
    74		// We need to clear 1 of these.
    75		// Avoid the expense of clearing the others (pointer write barrier).
    76		if i.bytes.str != nil {
    77			i.bytes.str = nil
    78		} else if i.reader.r != nil {
    79			i.reader.r = nil
    80		} else {
    81			i.string.str = ""
    82		}
    83	}
    84	
    85	func (i *inputs) init(r io.RuneReader, b []byte, s string) (input, int) {
    86		if r != nil {
    87			return i.newReader(r), 0
    88		}
    89		if b != nil {
    90			return i.newBytes(b), len(b)
    91		}
    92		return i.newString(s), len(s)
    93	}
    94	
    95	func (m *machine) init(ncap int) {
    96		for _, t := range m.pool {
    97			t.cap = t.cap[:ncap]
    98		}
    99		m.matchcap = m.matchcap[:ncap]
   100	}
   101	
   102	// alloc allocates a new thread with the given instruction.
   103	// It uses the free pool if possible.
   104	func (m *machine) alloc(i *syntax.Inst) *thread {
   105		var t *thread
   106		if n := len(m.pool); n > 0 {
   107			t = m.pool[n-1]
   108			m.pool = m.pool[:n-1]
   109		} else {
   110			t = new(thread)
   111			t.cap = make([]int, len(m.matchcap), cap(m.matchcap))
   112		}
   113		t.inst = i
   114		return t
   115	}
   116	
   117	// A lazyFlag is a lazily-evaluated syntax.EmptyOp,
   118	// for checking zero-width flags like ^ $ \A \z \B \b.
   119	// It records the pair of relevant runes and does not
   120	// determine the implied flags until absolutely necessary
   121	// (most of the time, that means never).
   122	type lazyFlag uint64
   123	
   124	func newLazyFlag(r1, r2 rune) lazyFlag {
   125		return lazyFlag(uint64(r1)<<32 | uint64(uint32(r2)))
   126	}
   127	
   128	func (f lazyFlag) match(op syntax.EmptyOp) bool {
   129		if op == 0 {
   130			return true
   131		}
   132		r1 := rune(f >> 32)
   133		if op&syntax.EmptyBeginLine != 0 {
   134			if r1 != '\n' && r1 >= 0 {
   135				return false
   136			}
   137			op &^= syntax.EmptyBeginLine
   138		}
   139		if op&syntax.EmptyBeginText != 0 {
   140			if r1 >= 0 {
   141				return false
   142			}
   143			op &^= syntax.EmptyBeginText
   144		}
   145		if op == 0 {
   146			return true
   147		}
   148		r2 := rune(f)
   149		if op&syntax.EmptyEndLine != 0 {
   150			if r2 != '\n' && r2 >= 0 {
   151				return false
   152			}
   153			op &^= syntax.EmptyEndLine
   154		}
   155		if op&syntax.EmptyEndText != 0 {
   156			if r2 >= 0 {
   157				return false
   158			}
   159			op &^= syntax.EmptyEndText
   160		}
   161		if op == 0 {
   162			return true
   163		}
   164		if syntax.IsWordChar(r1) != syntax.IsWordChar(r2) {
   165			op &^= syntax.EmptyWordBoundary
   166		} else {
   167			op &^= syntax.EmptyNoWordBoundary
   168		}
   169		return op == 0
   170	}
   171	
   172	// match runs the machine over the input starting at pos.
   173	// It reports whether a match was found.
   174	// If so, m.matchcap holds the submatch information.
   175	func (m *machine) match(i input, pos int) bool {
   176		startCond := m.re.cond
   177		if startCond == ^syntax.EmptyOp(0) { // impossible
   178			return false
   179		}
   180		m.matched = false
   181		for i := range m.matchcap {
   182			m.matchcap[i] = -1
   183		}
   184		runq, nextq := &m.q0, &m.q1
   185		r, r1 := endOfText, endOfText
   186		width, width1 := 0, 0
   187		r, width = i.step(pos)
   188		if r != endOfText {
   189			r1, width1 = i.step(pos + width)
   190		}
   191		var flag lazyFlag
   192		if pos == 0 {
   193			flag = newLazyFlag(-1, r)
   194		} else {
   195			flag = i.context(pos)
   196		}
   197		for {
   198			if len(runq.dense) == 0 {
   199				if startCond&syntax.EmptyBeginText != 0 && pos != 0 {
   200					// Anchored match, past beginning of text.
   201					break
   202				}
   203				if m.matched {
   204					// Have match; finished exploring alternatives.
   205					break
   206				}
   207				if len(m.re.prefix) > 0 && r1 != m.re.prefixRune && i.canCheckPrefix() {
   208					// Match requires literal prefix; fast search for it.
   209					advance := i.index(m.re, pos)
   210					if advance < 0 {
   211						break
   212					}
   213					pos += advance
   214					r, width = i.step(pos)
   215					r1, width1 = i.step(pos + width)
   216				}
   217			}
   218			if !m.matched {
   219				if len(m.matchcap) > 0 {
   220					m.matchcap[0] = pos
   221				}
   222				m.add(runq, uint32(m.p.Start), pos, m.matchcap, &flag, nil)
   223			}
   224			flag = newLazyFlag(r, r1)
   225			m.step(runq, nextq, pos, pos+width, r, &flag)
   226			if width == 0 {
   227				break
   228			}
   229			if len(m.matchcap) == 0 && m.matched {
   230				// Found a match and not paying attention
   231				// to where it is, so any match will do.
   232				break
   233			}
   234			pos += width
   235			r, width = r1, width1
   236			if r != endOfText {
   237				r1, width1 = i.step(pos + width)
   238			}
   239			runq, nextq = nextq, runq
   240		}
   241		m.clear(nextq)
   242		return m.matched
   243	}
   244	
   245	// clear frees all threads on the thread queue.
   246	func (m *machine) clear(q *queue) {
   247		for _, d := range q.dense {
   248			if d.t != nil {
   249				m.pool = append(m.pool, d.t)
   250			}
   251		}
   252		q.dense = q.dense[:0]
   253	}
   254	
   255	// step executes one step of the machine, running each of the threads
   256	// on runq and appending new threads to nextq.
   257	// The step processes the rune c (which may be endOfText),
   258	// which starts at position pos and ends at nextPos.
   259	// nextCond gives the setting for the empty-width flags after c.
   260	func (m *machine) step(runq, nextq *queue, pos, nextPos int, c rune, nextCond *lazyFlag) {
   261		longest := m.re.longest
   262		for j := 0; j < len(runq.dense); j++ {
   263			d := &runq.dense[j]
   264			t := d.t
   265			if t == nil {
   266				continue
   267			}
   268			if longest && m.matched && len(t.cap) > 0 && m.matchcap[0] < t.cap[0] {
   269				m.pool = append(m.pool, t)
   270				continue
   271			}
   272			i := t.inst
   273			add := false
   274			switch i.Op {
   275			default:
   276				panic("bad inst")
   277	
   278			case syntax.InstMatch:
   279				if len(t.cap) > 0 && (!longest || !m.matched || m.matchcap[1] < pos) {
   280					t.cap[1] = pos
   281					copy(m.matchcap, t.cap)
   282				}
   283				if !longest {
   284					// First-match mode: cut off all lower-priority threads.
   285					for _, d := range runq.dense[j+1:] {
   286						if d.t != nil {
   287							m.pool = append(m.pool, d.t)
   288						}
   289					}
   290					runq.dense = runq.dense[:0]
   291				}
   292				m.matched = true
   293	
   294			case syntax.InstRune:
   295				add = i.MatchRune(c)
   296			case syntax.InstRune1:
   297				add = c == i.Rune[0]
   298			case syntax.InstRuneAny:
   299				add = true
   300			case syntax.InstRuneAnyNotNL:
   301				add = c != '\n'
   302			}
   303			if add {
   304				t = m.add(nextq, i.Out, nextPos, t.cap, nextCond, t)
   305			}
   306			if t != nil {
   307				m.pool = append(m.pool, t)
   308			}
   309		}
   310		runq.dense = runq.dense[:0]
   311	}
   312	
   313	// add adds an entry to q for pc, unless the q already has such an entry.
   314	// It also recursively adds an entry for all instructions reachable from pc by following
   315	// empty-width conditions satisfied by cond.  pos gives the current position
   316	// in the input.
   317	func (m *machine) add(q *queue, pc uint32, pos int, cap []int, cond *lazyFlag, t *thread) *thread {
   318	Again:
   319		if pc == 0 {
   320			return t
   321		}
   322		if j := q.sparse[pc]; j < uint32(len(q.dense)) && q.dense[j].pc == pc {
   323			return t
   324		}
   325	
   326		j := len(q.dense)
   327		q.dense = q.dense[:j+1]
   328		d := &q.dense[j]
   329		d.t = nil
   330		d.pc = pc
   331		q.sparse[pc] = uint32(j)
   332	
   333		i := &m.p.Inst[pc]
   334		switch i.Op {
   335		default:
   336			panic("unhandled")
   337		case syntax.InstFail:
   338			// nothing
   339		case syntax.InstAlt, syntax.InstAltMatch:
   340			t = m.add(q, i.Out, pos, cap, cond, t)
   341			pc = i.Arg
   342			goto Again
   343		case syntax.InstEmptyWidth:
   344			if cond.match(syntax.EmptyOp(i.Arg)) {
   345				pc = i.Out
   346				goto Again
   347			}
   348		case syntax.InstNop:
   349			pc = i.Out
   350			goto Again
   351		case syntax.InstCapture:
   352			if int(i.Arg) < len(cap) {
   353				opos := cap[i.Arg]
   354				cap[i.Arg] = pos
   355				m.add(q, i.Out, pos, cap, cond, nil)
   356				cap[i.Arg] = opos
   357			} else {
   358				pc = i.Out
   359				goto Again
   360			}
   361		case syntax.InstMatch, syntax.InstRune, syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:
   362			if t == nil {
   363				t = m.alloc(i)
   364			} else {
   365				t.inst = i
   366			}
   367			if len(cap) > 0 && &t.cap[0] != &cap[0] {
   368				copy(t.cap, cap)
   369			}
   370			d.t = t
   371			t = nil
   372		}
   373		return t
   374	}
   375	
   376	type onePassMachine struct {
   377		inputs   inputs
   378		matchcap []int
   379	}
   380	
   381	var onePassPool sync.Pool
   382	
   383	func newOnePassMachine() *onePassMachine {
   384		m, ok := onePassPool.Get().(*onePassMachine)
   385		if !ok {
   386			m = new(onePassMachine)
   387		}
   388		return m
   389	}
   390	
   391	func freeOnePassMachine(m *onePassMachine) {
   392		m.inputs.clear()
   393		onePassPool.Put(m)
   394	}
   395	
   396	// doOnePass implements r.doExecute using the one-pass execution engine.
   397	func (re *Regexp) doOnePass(ir io.RuneReader, ib []byte, is string, pos, ncap int, dstCap []int) []int {
   398		startCond := re.cond
   399		if startCond == ^syntax.EmptyOp(0) { // impossible
   400			return nil
   401		}
   402	
   403		m := newOnePassMachine()
   404		if cap(m.matchcap) < ncap {
   405			m.matchcap = make([]int, ncap)
   406		} else {
   407			m.matchcap = m.matchcap[:ncap]
   408		}
   409	
   410		matched := false
   411		for i := range m.matchcap {
   412			m.matchcap[i] = -1
   413		}
   414	
   415		i, _ := m.inputs.init(ir, ib, is)
   416	
   417		r, r1 := endOfText, endOfText
   418		width, width1 := 0, 0
   419		r, width = i.step(pos)
   420		if r != endOfText {
   421			r1, width1 = i.step(pos + width)
   422		}
   423		var flag lazyFlag
   424		if pos == 0 {
   425			flag = newLazyFlag(-1, r)
   426		} else {
   427			flag = i.context(pos)
   428		}
   429		pc := re.onepass.Start
   430		inst := re.onepass.Inst[pc]
   431		// If there is a simple literal prefix, skip over it.
   432		if pos == 0 && flag.match(syntax.EmptyOp(inst.Arg)) &&
   433			len(re.prefix) > 0 && i.canCheckPrefix() {
   434			// Match requires literal prefix; fast search for it.
   435			if !i.hasPrefix(re) {
   436				goto Return
   437			}
   438			pos += len(re.prefix)
   439			r, width = i.step(pos)
   440			r1, width1 = i.step(pos + width)
   441			flag = i.context(pos)
   442			pc = int(re.prefixEnd)
   443		}
   444		for {
   445			inst = re.onepass.Inst[pc]
   446			pc = int(inst.Out)
   447			switch inst.Op {
   448			default:
   449				panic("bad inst")
   450			case syntax.InstMatch:
   451				matched = true
   452				if len(m.matchcap) > 0 {
   453					m.matchcap[0] = 0
   454					m.matchcap[1] = pos
   455				}
   456				goto Return
   457			case syntax.InstRune:
   458				if !inst.MatchRune(r) {
   459					goto Return
   460				}
   461			case syntax.InstRune1:
   462				if r != inst.Rune[0] {
   463					goto Return
   464				}
   465			case syntax.InstRuneAny:
   466				// Nothing
   467			case syntax.InstRuneAnyNotNL:
   468				if r == '\n' {
   469					goto Return
   470				}
   471			// peek at the input rune to see which branch of the Alt to take
   472			case syntax.InstAlt, syntax.InstAltMatch:
   473				pc = int(onePassNext(&inst, r))
   474				continue
   475			case syntax.InstFail:
   476				goto Return
   477			case syntax.InstNop:
   478				continue
   479			case syntax.InstEmptyWidth:
   480				if !flag.match(syntax.EmptyOp(inst.Arg)) {
   481					goto Return
   482				}
   483				continue
   484			case syntax.InstCapture:
   485				if int(inst.Arg) < len(m.matchcap) {
   486					m.matchcap[inst.Arg] = pos
   487				}
   488				continue
   489			}
   490			if width == 0 {
   491				break
   492			}
   493			flag = newLazyFlag(r, r1)
   494			pos += width
   495			r, width = r1, width1
   496			if r != endOfText {
   497				r1, width1 = i.step(pos + width)
   498			}
   499		}
   500	
   501	Return:
   502		if !matched {
   503			freeOnePassMachine(m)
   504			return nil
   505		}
   506	
   507		dstCap = append(dstCap, m.matchcap...)
   508		freeOnePassMachine(m)
   509		return dstCap
   510	}
   511	
   512	// doMatch reports whether either r, b or s match the regexp.
   513	func (re *Regexp) doMatch(r io.RuneReader, b []byte, s string) bool {
   514		return re.doExecute(r, b, s, 0, 0, nil) != nil
   515	}
   516	
   517	// doExecute finds the leftmost match in the input, appends the position
   518	// of its subexpressions to dstCap and returns dstCap.
   519	//
   520	// nil is returned if no matches are found and non-nil if matches are found.
   521	func (re *Regexp) doExecute(r io.RuneReader, b []byte, s string, pos int, ncap int, dstCap []int) []int {
   522		if dstCap == nil {
   523			// Make sure 'return dstCap' is non-nil.
   524			dstCap = arrayNoInts[:0:0]
   525		}
   526	
   527		if r == nil && len(b)+len(s) < re.minInputLen {
   528			return nil
   529		}
   530	
   531		if re.onepass != nil {
   532			return re.doOnePass(r, b, s, pos, ncap, dstCap)
   533		}
   534		if r == nil && len(b)+len(s) < re.maxBitStateLen {
   535			return re.backtrack(b, s, pos, ncap, dstCap)
   536		}
   537	
   538		m := re.get()
   539		i, _ := m.inputs.init(r, b, s)
   540	
   541		m.init(ncap)
   542		if !m.match(i, pos) {
   543			re.put(m)
   544			return nil
   545		}
   546	
   547		dstCap = append(dstCap, m.matchcap...)
   548		re.put(m)
   549		return dstCap
   550	}
   551	
   552	// arrayNoInts is returned by doExecute match if nil dstCap is passed
   553	// to it with ncap=0.
   554	var arrayNoInts [0]int
   555	

View as plain text