exec.go

Documentation: regexp

		 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