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	)
    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	}