...
Run Format

Source file src/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	)
    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		op             *onePassProg // compiled onepass program, or notOnePass
    41		maxBitStateLen int          // max length of string to search with bitstate
    42		b              *bitState    // state for backtracker, allocated lazily
    43		q0, q1         queue        // two queues for runq, nextq
    44		pool           []*thread    // pool of available threads
    45		matched        bool         // whether a match was found
    46		matchcap       []int        // capture information for the match
    47	
    48		// cached inputs, to avoid allocation
    49		inputBytes  inputBytes
    50		inputString inputString
    51		inputReader inputReader
    52	}
    53	
    54	func (m *machine) newInputBytes(b []byte) input {
    55		m.inputBytes.str = b
    56		return &m.inputBytes
    57	}
    58	
    59	func (m *machine) newInputString(s string) input {
    60		m.inputString.str = s
    61		return &m.inputString
    62	}
    63	
    64	func (m *machine) newInputReader(r io.RuneReader) input {
    65		m.inputReader.r = r
    66		m.inputReader.atEOT = false
    67		m.inputReader.pos = 0
    68		return &m.inputReader
    69	}
    70	
    71	// progMachine returns a new machine running the prog p.
    72	func progMachine(p *syntax.Prog, op *onePassProg) *machine {
    73		m := &machine{p: p, op: op}
    74		n := len(m.p.Inst)
    75		m.q0 = queue{make([]uint32, n), make([]entry, 0, n)}
    76		m.q1 = queue{make([]uint32, n), make([]entry, 0, n)}
    77		ncap := p.NumCap
    78		if ncap < 2 {
    79			ncap = 2
    80		}
    81		if op == notOnePass {
    82			m.maxBitStateLen = maxBitStateLen(p)
    83		}
    84		m.matchcap = make([]int, ncap)
    85		return m
    86	}
    87	
    88	func (m *machine) init(ncap int) {
    89		for _, t := range m.pool {
    90			t.cap = t.cap[:ncap]
    91		}
    92		m.matchcap = m.matchcap[:ncap]
    93	}
    94	
    95	// alloc allocates a new thread with the given instruction.
    96	// It uses the free pool if possible.
    97	func (m *machine) alloc(i *syntax.Inst) *thread {
    98		var t *thread
    99		if n := len(m.pool); n > 0 {
   100			t = m.pool[n-1]
   101			m.pool = m.pool[:n-1]
   102		} else {
   103			t = new(thread)
   104			t.cap = make([]int, len(m.matchcap), cap(m.matchcap))
   105		}
   106		t.inst = i
   107		return t
   108	}
   109	
   110	// match runs the machine over the input starting at pos.
   111	// It reports whether a match was found.
   112	// If so, m.matchcap holds the submatch information.
   113	func (m *machine) match(i input, pos int) bool {
   114		startCond := m.re.cond
   115		if startCond == ^syntax.EmptyOp(0) { // impossible
   116			return false
   117		}
   118		m.matched = false
   119		for i := range m.matchcap {
   120			m.matchcap[i] = -1
   121		}
   122		runq, nextq := &m.q0, &m.q1
   123		r, r1 := endOfText, endOfText
   124		width, width1 := 0, 0
   125		r, width = i.step(pos)
   126		if r != endOfText {
   127			r1, width1 = i.step(pos + width)
   128		}
   129		var flag syntax.EmptyOp
   130		if pos == 0 {
   131			flag = syntax.EmptyOpContext(-1, r)
   132		} else {
   133			flag = i.context(pos)
   134		}
   135		for {
   136			if len(runq.dense) == 0 {
   137				if startCond&syntax.EmptyBeginText != 0 && pos != 0 {
   138					// Anchored match, past beginning of text.
   139					break
   140				}
   141				if m.matched {
   142					// Have match; finished exploring alternatives.
   143					break
   144				}
   145				if len(m.re.prefix) > 0 && r1 != m.re.prefixRune && i.canCheckPrefix() {
   146					// Match requires literal prefix; fast search for it.
   147					advance := i.index(m.re, pos)
   148					if advance < 0 {
   149						break
   150					}
   151					pos += advance
   152					r, width = i.step(pos)
   153					r1, width1 = i.step(pos + width)
   154				}
   155			}
   156			if !m.matched {
   157				if len(m.matchcap) > 0 {
   158					m.matchcap[0] = pos
   159				}
   160				m.add(runq, uint32(m.p.Start), pos, m.matchcap, flag, nil)
   161			}
   162			flag = syntax.EmptyOpContext(r, r1)
   163			m.step(runq, nextq, pos, pos+width, r, flag)
   164			if width == 0 {
   165				break
   166			}
   167			if len(m.matchcap) == 0 && m.matched {
   168				// Found a match and not paying attention
   169				// to where it is, so any match will do.
   170				break
   171			}
   172			pos += width
   173			r, width = r1, width1
   174			if r != endOfText {
   175				r1, width1 = i.step(pos + width)
   176			}
   177			runq, nextq = nextq, runq
   178		}
   179		m.clear(nextq)
   180		return m.matched
   181	}
   182	
   183	// clear frees all threads on the thread queue.
   184	func (m *machine) clear(q *queue) {
   185		for _, d := range q.dense {
   186			if d.t != nil {
   187				m.pool = append(m.pool, d.t)
   188			}
   189		}
   190		q.dense = q.dense[:0]
   191	}
   192	
   193	// step executes one step of the machine, running each of the threads
   194	// on runq and appending new threads to nextq.
   195	// The step processes the rune c (which may be endOfText),
   196	// which starts at position pos and ends at nextPos.
   197	// nextCond gives the setting for the empty-width flags after c.
   198	func (m *machine) step(runq, nextq *queue, pos, nextPos int, c rune, nextCond syntax.EmptyOp) {
   199		longest := m.re.longest
   200		for j := 0; j < len(runq.dense); j++ {
   201			d := &runq.dense[j]
   202			t := d.t
   203			if t == nil {
   204				continue
   205			}
   206			if longest && m.matched && len(t.cap) > 0 && m.matchcap[0] < t.cap[0] {
   207				m.pool = append(m.pool, t)
   208				continue
   209			}
   210			i := t.inst
   211			add := false
   212			switch i.Op {
   213			default:
   214				panic("bad inst")
   215	
   216			case syntax.InstMatch:
   217				if len(t.cap) > 0 && (!longest || !m.matched || m.matchcap[1] < pos) {
   218					t.cap[1] = pos
   219					copy(m.matchcap, t.cap)
   220				}
   221				if !longest {
   222					// First-match mode: cut off all lower-priority threads.
   223					for _, d := range runq.dense[j+1:] {
   224						if d.t != nil {
   225							m.pool = append(m.pool, d.t)
   226						}
   227					}
   228					runq.dense = runq.dense[:0]
   229				}
   230				m.matched = true
   231	
   232			case syntax.InstRune:
   233				add = i.MatchRune(c)
   234			case syntax.InstRune1:
   235				add = c == i.Rune[0]
   236			case syntax.InstRuneAny:
   237				add = true
   238			case syntax.InstRuneAnyNotNL:
   239				add = c != '\n'
   240			}
   241			if add {
   242				t = m.add(nextq, i.Out, nextPos, t.cap, nextCond, t)
   243			}
   244			if t != nil {
   245				m.pool = append(m.pool, t)
   246			}
   247		}
   248		runq.dense = runq.dense[:0]
   249	}
   250	
   251	// add adds an entry to q for pc, unless the q already has such an entry.
   252	// It also recursively adds an entry for all instructions reachable from pc by following
   253	// empty-width conditions satisfied by cond.  pos gives the current position
   254	// in the input.
   255	func (m *machine) add(q *queue, pc uint32, pos int, cap []int, cond syntax.EmptyOp, t *thread) *thread {
   256		if pc == 0 {
   257			return t
   258		}
   259		if j := q.sparse[pc]; j < uint32(len(q.dense)) && q.dense[j].pc == pc {
   260			return t
   261		}
   262	
   263		j := len(q.dense)
   264		q.dense = q.dense[:j+1]
   265		d := &q.dense[j]
   266		d.t = nil
   267		d.pc = pc
   268		q.sparse[pc] = uint32(j)
   269	
   270		i := &m.p.Inst[pc]
   271		switch i.Op {
   272		default:
   273			panic("unhandled")
   274		case syntax.InstFail:
   275			// nothing
   276		case syntax.InstAlt, syntax.InstAltMatch:
   277			t = m.add(q, i.Out, pos, cap, cond, t)
   278			t = m.add(q, i.Arg, pos, cap, cond, t)
   279		case syntax.InstEmptyWidth:
   280			if syntax.EmptyOp(i.Arg)&^cond == 0 {
   281				t = m.add(q, i.Out, pos, cap, cond, t)
   282			}
   283		case syntax.InstNop:
   284			t = m.add(q, i.Out, pos, cap, cond, t)
   285		case syntax.InstCapture:
   286			if int(i.Arg) < len(cap) {
   287				opos := cap[i.Arg]
   288				cap[i.Arg] = pos
   289				m.add(q, i.Out, pos, cap, cond, nil)
   290				cap[i.Arg] = opos
   291			} else {
   292				t = m.add(q, i.Out, pos, cap, cond, t)
   293			}
   294		case syntax.InstMatch, syntax.InstRune, syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:
   295			if t == nil {
   296				t = m.alloc(i)
   297			} else {
   298				t.inst = i
   299			}
   300			if len(cap) > 0 && &t.cap[0] != &cap[0] {
   301				copy(t.cap, cap)
   302			}
   303			d.t = t
   304			t = nil
   305		}
   306		return t
   307	}
   308	
   309	// onepass runs the machine over the input starting at pos.
   310	// It reports whether a match was found.
   311	// If so, m.matchcap holds the submatch information.
   312	func (m *machine) onepass(i input, pos int) bool {
   313		startCond := m.re.cond
   314		if startCond == ^syntax.EmptyOp(0) { // impossible
   315			return false
   316		}
   317		m.matched = false
   318		for i := range m.matchcap {
   319			m.matchcap[i] = -1
   320		}
   321		r, r1 := endOfText, endOfText
   322		width, width1 := 0, 0
   323		r, width = i.step(pos)
   324		if r != endOfText {
   325			r1, width1 = i.step(pos + width)
   326		}
   327		var flag syntax.EmptyOp
   328		if pos == 0 {
   329			flag = syntax.EmptyOpContext(-1, r)
   330		} else {
   331			flag = i.context(pos)
   332		}
   333		pc := m.op.Start
   334		inst := m.op.Inst[pc]
   335		// If there is a simple literal prefix, skip over it.
   336		if pos == 0 && syntax.EmptyOp(inst.Arg)&^flag == 0 &&
   337			len(m.re.prefix) > 0 && i.canCheckPrefix() {
   338			// Match requires literal prefix; fast search for it.
   339			if i.hasPrefix(m.re) {
   340				pos += len(m.re.prefix)
   341				r, width = i.step(pos)
   342				r1, width1 = i.step(pos + width)
   343				flag = i.context(pos)
   344				pc = int(m.re.prefixEnd)
   345			} else {
   346				return m.matched
   347			}
   348		}
   349		for {
   350			inst = m.op.Inst[pc]
   351			pc = int(inst.Out)
   352			switch inst.Op {
   353			default:
   354				panic("bad inst")
   355			case syntax.InstMatch:
   356				m.matched = true
   357				if len(m.matchcap) > 0 {
   358					m.matchcap[0] = 0
   359					m.matchcap[1] = pos
   360				}
   361				return m.matched
   362			case syntax.InstRune:
   363				if !inst.MatchRune(r) {
   364					return m.matched
   365				}
   366			case syntax.InstRune1:
   367				if r != inst.Rune[0] {
   368					return m.matched
   369				}
   370			case syntax.InstRuneAny:
   371				// Nothing
   372			case syntax.InstRuneAnyNotNL:
   373				if r == '\n' {
   374					return m.matched
   375				}
   376			// peek at the input rune to see which branch of the Alt to take
   377			case syntax.InstAlt, syntax.InstAltMatch:
   378				pc = int(onePassNext(&inst, r))
   379				continue
   380			case syntax.InstFail:
   381				return m.matched
   382			case syntax.InstNop:
   383				continue
   384			case syntax.InstEmptyWidth:
   385				if syntax.EmptyOp(inst.Arg)&^flag != 0 {
   386					return m.matched
   387				}
   388				continue
   389			case syntax.InstCapture:
   390				if int(inst.Arg) < len(m.matchcap) {
   391					m.matchcap[inst.Arg] = pos
   392				}
   393				continue
   394			}
   395			if width == 0 {
   396				break
   397			}
   398			flag = syntax.EmptyOpContext(r, r1)
   399			pos += width
   400			r, width = r1, width1
   401			if r != endOfText {
   402				r1, width1 = i.step(pos + width)
   403			}
   404		}
   405		return m.matched
   406	}
   407	
   408	// doMatch reports whether either r, b or s match the regexp.
   409	func (re *Regexp) doMatch(r io.RuneReader, b []byte, s string) bool {
   410		return re.doExecute(r, b, s, 0, 0, nil) != nil
   411	}
   412	
   413	// doExecute finds the leftmost match in the input, appends the position
   414	// of its subexpressions to dstCap and returns dstCap.
   415	//
   416	// nil is returned if no matches are found and non-nil if matches are found.
   417	func (re *Regexp) doExecute(r io.RuneReader, b []byte, s string, pos int, ncap int, dstCap []int) []int {
   418		m := re.get()
   419		var i input
   420		var size int
   421		if r != nil {
   422			i = m.newInputReader(r)
   423		} else if b != nil {
   424			i = m.newInputBytes(b)
   425			size = len(b)
   426		} else {
   427			i = m.newInputString(s)
   428			size = len(s)
   429		}
   430		if m.op != notOnePass {
   431			if !m.onepass(i, pos) {
   432				re.put(m)
   433				return nil
   434			}
   435		} else if size < m.maxBitStateLen && r == nil {
   436			if m.b == nil {
   437				m.b = newBitState(m.p)
   438			}
   439			if !m.backtrack(i, pos, size, ncap) {
   440				re.put(m)
   441				return nil
   442			}
   443		} else {
   444			m.init(ncap)
   445			if !m.match(i, pos) {
   446				re.put(m)
   447				return nil
   448			}
   449		}
   450		dstCap = append(dstCap, m.matchcap...)
   451		if dstCap == nil {
   452			// Keep the promise of returning non-nil value on match.
   453			dstCap = arrayNoInts[:0]
   454		}
   455		re.put(m)
   456		return dstCap
   457	}
   458	
   459	// arrayNoInts is returned by doExecute match if nil dstCap is passed
   460	// to it with ncap=0.
   461	var arrayNoInts [0]int
   462	

View as plain text