// 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 (
	
	
	
)

// 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 ( *inputs) ( []byte) input {
	.bytes.str = 
	return &.bytes
}

func ( *inputs) ( string) input {
	.string.str = 
	return &.string
}

func ( *inputs) ( io.RuneReader) input {
	.reader.r = 
	.reader.atEOT = false
	.reader.pos = 0
	return &.reader
}

func ( *inputs) () {
	// We need to clear 1 of these.
	// Avoid the expense of clearing the others (pointer write barrier).
	if .bytes.str != nil {
		.bytes.str = nil
	} else if .reader.r != nil {
		.reader.r = nil
	} else {
		.string.str = ""
	}
}

func ( *inputs) ( io.RuneReader,  []byte,  string) (input, int) {
	if  != nil {
		return .newReader(), 0
	}
	if  != nil {
		return .newBytes(), len()
	}
	return .newString(), len()
}

func ( *machine) ( int) {
	for ,  := range .pool {
		.cap = .cap[:]
	}
	.matchcap = .matchcap[:]
}

// alloc allocates a new thread with the given instruction.
// It uses the free pool if possible.
func ( *machine) ( *syntax.Inst) *thread {
	var  *thread
	if  := len(.pool);  > 0 {
		 = .pool[-1]
		.pool = .pool[:-1]
	} else {
		 = new(thread)
		.cap = make([]int, len(.matchcap), cap(.matchcap))
	}
	.inst = 
	return 
}

// 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 (,  rune) lazyFlag {
	return lazyFlag(uint64()<<32 | uint64(uint32()))
}

func ( lazyFlag) ( syntax.EmptyOp) bool {
	if  == 0 {
		return true
	}
	 := rune( >> 32)
	if &syntax.EmptyBeginLine != 0 {
		if  != '\n' &&  >= 0 {
			return false
		}
		 &^= syntax.EmptyBeginLine
	}
	if &syntax.EmptyBeginText != 0 {
		if  >= 0 {
			return false
		}
		 &^= syntax.EmptyBeginText
	}
	if  == 0 {
		return true
	}
	 := rune()
	if &syntax.EmptyEndLine != 0 {
		if  != '\n' &&  >= 0 {
			return false
		}
		 &^= syntax.EmptyEndLine
	}
	if &syntax.EmptyEndText != 0 {
		if  >= 0 {
			return false
		}
		 &^= syntax.EmptyEndText
	}
	if  == 0 {
		return true
	}
	if syntax.IsWordChar() != syntax.IsWordChar() {
		 &^= syntax.EmptyWordBoundary
	} else {
		 &^= syntax.EmptyNoWordBoundary
	}
	return  == 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 ( *machine) ( input,  int) bool {
	 := .re.cond
	if  == ^syntax.EmptyOp(0) { // impossible
		return false
	}
	.matched = false
	for  := range .matchcap {
		.matchcap[] = -1
	}
	,  := &.q0, &.q1
	,  := endOfText, endOfText
	,  := 0, 0
	,  = .step()
	if  != endOfText {
		,  = .step( + )
	}
	var  lazyFlag
	if  == 0 {
		 = newLazyFlag(-1, )
	} else {
		 = .context()
	}
	for {
		if len(.dense) == 0 {
			if &syntax.EmptyBeginText != 0 &&  != 0 {
				// Anchored match, past beginning of text.
				break
			}
			if .matched {
				// Have match; finished exploring alternatives.
				break
			}
			if len(.re.prefix) > 0 &&  != .re.prefixRune && .canCheckPrefix() {
				// Match requires literal prefix; fast search for it.
				 := .index(.re, )
				if  < 0 {
					break
				}
				 += 
				,  = .step()
				,  = .step( + )
			}
		}
		if !.matched {
			if len(.matchcap) > 0 {
				.matchcap[0] = 
			}
			.add(, uint32(.p.Start), , .matchcap, &, nil)
		}
		 = newLazyFlag(, )
		.step(, , , +, , &)
		if  == 0 {
			break
		}
		if len(.matchcap) == 0 && .matched {
			// Found a match and not paying attention
			// to where it is, so any match will do.
			break
		}
		 += 
		,  = , 
		if  != endOfText {
			,  = .step( + )
		}
		,  = , 
	}
	.clear()
	return .matched
}

// clear frees all threads on the thread queue.
func ( *machine) ( *queue) {
	for ,  := range .dense {
		if .t != nil {
			.pool = append(.pool, .t)
		}
	}
	.dense = .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 ( *machine) (,  *queue, ,  int,  rune,  *lazyFlag) {
	 := .re.longest
	for  := 0;  < len(.dense); ++ {
		 := &.dense[]
		 := .t
		if  == nil {
			continue
		}
		if  && .matched && len(.cap) > 0 && .matchcap[0] < .cap[0] {
			.pool = append(.pool, )
			continue
		}
		 := .inst
		 := false
		switch .Op {
		default:
			panic("bad inst")

		case syntax.InstMatch:
			if len(.cap) > 0 && (! || !.matched || .matchcap[1] < ) {
				.cap[1] = 
				copy(.matchcap, .cap)
			}
			if ! {
				// First-match mode: cut off all lower-priority threads.
				for ,  := range .dense[+1:] {
					if .t != nil {
						.pool = append(.pool, .t)
					}
				}
				.dense = .dense[:0]
			}
			.matched = true

		case syntax.InstRune:
			 = .MatchRune()
		case syntax.InstRune1:
			 =  == .Rune[0]
		case syntax.InstRuneAny:
			 = true
		case syntax.InstRuneAnyNotNL:
			 =  != '\n'
		}
		if  {
			 = .add(, .Out, , .cap, , )
		}
		if  != nil {
			.pool = append(.pool, )
		}
	}
	.dense = .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 ( *machine) ( *queue,  uint32,  int,  []int,  *lazyFlag,  *thread) *thread {
:
	if  == 0 {
		return 
	}
	if  := .sparse[];  < uint32(len(.dense)) && .dense[].pc ==  {
		return 
	}

	 := len(.dense)
	.dense = .dense[:+1]
	 := &.dense[]
	.t = nil
	.pc = 
	.sparse[] = uint32()

	 := &.p.Inst[]
	switch .Op {
	default:
		panic("unhandled")
	case syntax.InstFail:
		// nothing
	case syntax.InstAlt, syntax.InstAltMatch:
		 = .(, .Out, , , , )
		 = .Arg
		goto 
	case syntax.InstEmptyWidth:
		if .match(syntax.EmptyOp(.Arg)) {
			 = .Out
			goto 
		}
	case syntax.InstNop:
		 = .Out
		goto 
	case syntax.InstCapture:
		if int(.Arg) < len() {
			 := [.Arg]
			[.Arg] = 
			.(, .Out, , , , nil)
			[.Arg] = 
		} else {
			 = .Out
			goto 
		}
	case syntax.InstMatch, syntax.InstRune, syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:
		if  == nil {
			 = .alloc()
		} else {
			.inst = 
		}
		if len() > 0 && &.cap[0] != &[0] {
			copy(.cap, )
		}
		.t = 
		 = nil
	}
	return 
}

type onePassMachine struct {
	inputs   inputs
	matchcap []int
}

var onePassPool sync.Pool

func () *onePassMachine {
	,  := onePassPool.Get().(*onePassMachine)
	if ! {
		 = new(onePassMachine)
	}
	return 
}

func ( *onePassMachine) {
	.inputs.clear()
	onePassPool.Put()
}

// doOnePass implements r.doExecute using the one-pass execution engine.
func ( *Regexp) ( io.RuneReader,  []byte,  string, ,  int,  []int) []int {
	 := .cond
	if  == ^syntax.EmptyOp(0) { // impossible
		return nil
	}

	 := newOnePassMachine()
	if cap(.matchcap) <  {
		.matchcap = make([]int, )
	} else {
		.matchcap = .matchcap[:]
	}

	 := false
	for  := range .matchcap {
		.matchcap[] = -1
	}

	,  := .inputs.init(, , )

	,  := endOfText, endOfText
	,  := 0, 0
	,  = .step()
	if  != endOfText {
		,  = .step( + )
	}
	var  lazyFlag
	if  == 0 {
		 = newLazyFlag(-1, )
	} else {
		 = .context()
	}
	 := .onepass.Start
	 := &.onepass.Inst[]
	// If there is a simple literal prefix, skip over it.
	if  == 0 && .match(syntax.EmptyOp(.Arg)) &&
		len(.prefix) > 0 && .canCheckPrefix() {
		// Match requires literal prefix; fast search for it.
		if !.hasPrefix() {
			goto 
		}
		 += len(.prefix)
		,  = .step()
		,  = .step( + )
		 = .context()
		 = int(.prefixEnd)
	}
	for {
		 = &.onepass.Inst[]
		 = int(.Out)
		switch .Op {
		default:
			panic("bad inst")
		case syntax.InstMatch:
			 = true
			if len(.matchcap) > 0 {
				.matchcap[0] = 0
				.matchcap[1] = 
			}
			goto 
		case syntax.InstRune:
			if !.MatchRune() {
				goto 
			}
		case syntax.InstRune1:
			if  != .Rune[0] {
				goto 
			}
		case syntax.InstRuneAny:
			// Nothing
		case syntax.InstRuneAnyNotNL:
			if  == '\n' {
				goto 
			}
		// peek at the input rune to see which branch of the Alt to take
		case syntax.InstAlt, syntax.InstAltMatch:
			 = int(onePassNext(, ))
			continue
		case syntax.InstFail:
			goto 
		case syntax.InstNop:
			continue
		case syntax.InstEmptyWidth:
			if !.match(syntax.EmptyOp(.Arg)) {
				goto 
			}
			continue
		case syntax.InstCapture:
			if int(.Arg) < len(.matchcap) {
				.matchcap[.Arg] = 
			}
			continue
		}
		if  == 0 {
			break
		}
		 = newLazyFlag(, )
		 += 
		,  = , 
		if  != endOfText {
			,  = .step( + )
		}
	}

:
	if ! {
		freeOnePassMachine()
		return nil
	}

	 = append(, .matchcap...)
	freeOnePassMachine()
	return 
}

// doMatch reports whether either r, b or s match the regexp.
func ( *Regexp) ( io.RuneReader,  []byte,  string) bool {
	return .doExecute(, , , 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 ( *Regexp) ( io.RuneReader,  []byte,  string,  int,  int,  []int) []int {
	if  == nil {
		// Make sure 'return dstCap' is non-nil.
		 = arrayNoInts[:0:0]
	}

	if  == nil && len()+len() < .minInputLen {
		return nil
	}

	if .onepass != nil {
		return .doOnePass(, , , , , )
	}
	if  == nil && len()+len() < .maxBitStateLen {
		return .backtrack(, , , , )
	}

	 := .get()
	,  := .inputs.init(, , )

	.init()
	if !.match(, ) {
		.put()
		return nil
	}

	 = append(, .matchcap...)
	.put()
	return 
}

// arrayNoInts is returned by doExecute match if nil dstCap is passed
// to it with ncap=0.
var arrayNoInts [0]int