// 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 syntax

import "unicode"

// A patchList is a list of instruction pointers that need to be filled in (patched).
// Because the pointers haven't been filled in yet, we can reuse their storage
// to hold the list. It's kind of sleazy, but works well in practice.
// See https://swtch.com/~rsc/regexp/regexp1.html for inspiration.
//
// These aren't really pointers: they're integers, so we can reinterpret them
// this way without using package unsafe. A value l.head denotes
// p.inst[l.head>>1].Out (l.head&1==0) or .Arg (l.head&1==1).
// head == 0 denotes the empty list, okay because we start every program
// with a fail instruction, so we'll never want to point at its output link.
type patchList struct {
	head, tail uint32
}

func makePatchList( uint32) patchList {
	return patchList{, }
}

func ( patchList) ( *Prog,  uint32) {
	 := .head
	for  != 0 {
		 := &.Inst[>>1]
		if &1 == 0 {
			 = .Out
			.Out = 
		} else {
			 = .Arg
			.Arg = 
		}
	}
}

func ( patchList) ( *Prog,  patchList) patchList {
	if .head == 0 {
		return 
	}
	if .head == 0 {
		return 
	}

	 := &.Inst[.tail>>1]
	if .tail&1 == 0 {
		.Out = .head
	} else {
		.Arg = .head
	}
	return patchList{.head, .tail}
}

// A frag represents a compiled program fragment.
type frag struct {
	i   uint32    // index of first instruction
	out patchList // where to record end instruction
}

type compiler struct {
	p *Prog
}

// Compile compiles the regexp into a program to be executed.
// The regexp should have been simplified already (returned from re.Simplify).
func ( *Regexp) (*Prog, error) {
	var  compiler
	.init()
	 := .compile()
	.out.patch(.p, .inst(InstMatch).i)
	.p.Start = int(.i)
	return .p, nil
}

func ( *compiler) () {
	.p = new(Prog)
	.p.NumCap = 2 // implicit ( and ) for whole match $0
	.inst(InstFail)
}

var anyRuneNotNL = []rune{0, '\n' - 1, '\n' + 1, unicode.MaxRune}
var anyRune = []rune{0, unicode.MaxRune}

func ( *compiler) ( *Regexp) frag {
	switch .Op {
	case OpNoMatch:
		return .fail()
	case OpEmptyMatch:
		return .nop()
	case OpLiteral:
		if len(.Rune) == 0 {
			return .nop()
		}
		var  frag
		for  := range .Rune {
			 := .rune(.Rune[:+1], .Flags)
			if  == 0 {
				 = 
			} else {
				 = .cat(, )
			}
		}
		return 
	case OpCharClass:
		return .rune(.Rune, .Flags)
	case OpAnyCharNotNL:
		return .rune(anyRuneNotNL, 0)
	case OpAnyChar:
		return .rune(anyRune, 0)
	case OpBeginLine:
		return .empty(EmptyBeginLine)
	case OpEndLine:
		return .empty(EmptyEndLine)
	case OpBeginText:
		return .empty(EmptyBeginText)
	case OpEndText:
		return .empty(EmptyEndText)
	case OpWordBoundary:
		return .empty(EmptyWordBoundary)
	case OpNoWordBoundary:
		return .empty(EmptyNoWordBoundary)
	case OpCapture:
		 := .cap(uint32(.Cap << 1))
		 := .(.Sub[0])
		 := .cap(uint32(.Cap<<1 | 1))
		return .cat(.cat(, ), )
	case OpStar:
		return .star(.(.Sub[0]), .Flags&NonGreedy != 0)
	case OpPlus:
		return .plus(.(.Sub[0]), .Flags&NonGreedy != 0)
	case OpQuest:
		return .quest(.(.Sub[0]), .Flags&NonGreedy != 0)
	case OpConcat:
		if len(.Sub) == 0 {
			return .nop()
		}
		var  frag
		for ,  := range .Sub {
			if  == 0 {
				 = .()
			} else {
				 = .cat(, .())
			}
		}
		return 
	case OpAlternate:
		var  frag
		for ,  := range .Sub {
			 = .alt(, .())
		}
		return 
	}
	panic("regexp: unhandled case in compile")
}

func ( *compiler) ( InstOp) frag {
	// TODO: impose length limit
	 := frag{i: uint32(len(.p.Inst))}
	.p.Inst = append(.p.Inst, Inst{Op: })
	return 
}

func ( *compiler) () frag {
	 := .inst(InstNop)
	.out = makePatchList(.i << 1)
	return 
}

func ( *compiler) () frag {
	return frag{}
}

func ( *compiler) ( uint32) frag {
	 := .inst(InstCapture)
	.out = makePatchList(.i << 1)
	.p.Inst[.i].Arg = 

	if .p.NumCap < int()+1 {
		.p.NumCap = int() + 1
	}
	return 
}

func ( *compiler) (,  frag) frag {
	// concat of failure is failure
	if .i == 0 || .i == 0 {
		return frag{}
	}

	// TODO: elide nop

	.out.patch(.p, .i)
	return frag{.i, .out}
}

func ( *compiler) (,  frag) frag {
	// alt of failure is other
	if .i == 0 {
		return 
	}
	if .i == 0 {
		return 
	}

	 := .inst(InstAlt)
	 := &.p.Inst[.i]
	.Out = .i
	.Arg = .i
	.out = .out.append(.p, .out)
	return 
}

func ( *compiler) ( frag,  bool) frag {
	 := .inst(InstAlt)
	 := &.p.Inst[.i]
	if  {
		.Arg = .i
		.out = makePatchList(.i << 1)
	} else {
		.Out = .i
		.out = makePatchList(.i<<1 | 1)
	}
	.out = .out.append(.p, .out)
	return 
}

func ( *compiler) ( frag,  bool) frag {
	 := .inst(InstAlt)
	 := &.p.Inst[.i]
	if  {
		.Arg = .i
		.out = makePatchList(.i << 1)
	} else {
		.Out = .i
		.out = makePatchList(.i<<1 | 1)
	}
	.out.patch(.p, .i)
	return 
}

func ( *compiler) ( frag,  bool) frag {
	return frag{.i, .star(, ).out}
}

func ( *compiler) ( EmptyOp) frag {
	 := .inst(InstEmptyWidth)
	.p.Inst[.i].Arg = uint32()
	.out = makePatchList(.i << 1)
	return 
}

func ( *compiler) ( []rune,  Flags) frag {
	 := .inst(InstRune)
	 := &.p.Inst[.i]
	.Rune = 
	 &= FoldCase // only relevant flag is FoldCase
	if len() != 1 || unicode.SimpleFold([0]) == [0] {
		// and sometimes not even that
		 &^= FoldCase
	}
	.Arg = uint32()
	.out = makePatchList(.i << 1)

	// Special cases for exec machine.
	switch {
	case &FoldCase == 0 && (len() == 1 || len() == 2 && [0] == [1]):
		.Op = InstRune1
	case len() == 2 && [0] == 0 && [1] == unicode.MaxRune:
		.Op = InstRuneAny
	case len() == 4 && [0] == 0 && [1] == '\n'-1 && [2] == '\n'+1 && [3] == unicode.MaxRune:
		.Op = InstRuneAnyNotNL
	}

	return 
}