// 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 parse builds parse trees for templates as defined by text/template
// and html/template. Clients should use those packages to construct templates
// rather than this one, which provides shared internal data structures not
// intended for general use.
package parse

import (
	
	
	
	
	
)

// Tree is the representation of a single parsed template.
type Tree struct {
	Name      string    // name of the template represented by the tree.
	ParseName string    // name of the top-level template during parsing, for error messages.
	Root      *ListNode // top-level root of the tree.
	Mode      Mode      // parsing mode.
	text      string    // text parsed to create the template (or its parent)
	// Parsing only; cleared after parse.
	funcs      []map[string]any
	lex        *lexer
	token      [3]item // three-token lookahead for parser.
	peekCount  int
	vars       []string // variables defined at the moment.
	treeSet    map[string]*Tree
	actionLine int // line of left delim starting action
	rangeDepth int
}

// A mode value is a set of flags (or 0). Modes control parser behavior.
type Mode uint

const (
	ParseComments Mode = 1 << iota // parse comments and add them to AST
	SkipFuncCheck                  // do not check that functions are defined
)

// Copy returns a copy of the [Tree]. Any parsing state is discarded.
func ( *Tree) () *Tree {
	if  == nil {
		return nil
	}
	return &Tree{
		Name:      .Name,
		ParseName: .ParseName,
		Root:      .Root.CopyList(),
		text:      .text,
	}
}

// Parse returns a map from template name to [Tree], created by parsing the
// templates described in the argument string. The top-level template will be
// given the specified name. If an error is encountered, parsing stops and an
// empty map is returned with the error.
func (, , ,  string,  ...map[string]any) (map[string]*Tree, error) {
	 := make(map[string]*Tree)
	 := New()
	.text = 
	,  := .Parse(, , , , ...)
	return , 
}

// next returns the next token.
func ( *Tree) () item {
	if .peekCount > 0 {
		.peekCount--
	} else {
		.token[0] = .lex.nextItem()
	}
	return .token[.peekCount]
}

// backup backs the input stream up one token.
func ( *Tree) () {
	.peekCount++
}

// backup2 backs the input stream up two tokens.
// The zeroth token is already there.
func ( *Tree) ( item) {
	.token[1] = 
	.peekCount = 2
}

// backup3 backs the input stream up three tokens
// The zeroth token is already there.
func ( *Tree) (,  item) { // Reverse order: we're pushing back.
	.token[1] = 
	.token[2] = 
	.peekCount = 3
}

// peek returns but does not consume the next token.
func ( *Tree) () item {
	if .peekCount > 0 {
		return .token[.peekCount-1]
	}
	.peekCount = 1
	.token[0] = .lex.nextItem()
	return .token[0]
}

// nextNonSpace returns the next non-space token.
func ( *Tree) () ( item) {
	for {
		 = .next()
		if .typ != itemSpace {
			break
		}
	}
	return 
}

// peekNonSpace returns but does not consume the next non-space token.
func ( *Tree) () item {
	 := .nextNonSpace()
	.backup()
	return 
}

// Parsing.

// New allocates a new parse tree with the given name.
func ( string,  ...map[string]any) *Tree {
	return &Tree{
		Name:  ,
		funcs: ,
	}
}

// ErrorContext returns a textual representation of the location of the node in the input text.
// The receiver is only used when the node does not have a pointer to the tree inside,
// which can occur in old code.
func ( *Tree) ( Node) (,  string) {
	 := int(.Position())
	 := .tree()
	if  == nil {
		 = 
	}
	 := .text[:]
	 := strings.LastIndex(, "\n")
	if  == -1 {
		 =  // On first line.
	} else {
		++ // After the newline.
		 =  - 
	}
	 := 1 + strings.Count(, "\n")
	 = .String()
	return fmt.Sprintf("%s:%d:%d", .ParseName, , ), 
}

// errorf formats the error and terminates processing.
func ( *Tree) ( string,  ...any) {
	.Root = nil
	 = fmt.Sprintf("template: %s:%d: %s", .ParseName, .token[0].line, )
	panic(fmt.Errorf(, ...))
}

// error terminates processing.
func ( *Tree) ( error) {
	.errorf("%s", )
}

// expect consumes the next token and guarantees it has the required type.
func ( *Tree) ( itemType,  string) item {
	 := .nextNonSpace()
	if .typ !=  {
		.unexpected(, )
	}
	return 
}

// expectOneOf consumes the next token and guarantees it has one of the required types.
func ( *Tree) (,  itemType,  string) item {
	 := .nextNonSpace()
	if .typ !=  && .typ !=  {
		.unexpected(, )
	}
	return 
}

// unexpected complains about the token and terminates processing.
func ( *Tree) ( item,  string) {
	if .typ == itemError {
		 := ""
		if .actionLine != 0 && .actionLine != .line {
			 = fmt.Sprintf(" in action started at %s:%d", .ParseName, .actionLine)
			if strings.HasSuffix(.val, " action") {
				 = [len(" in action"):] // avoid "action in action"
			}
		}
		.errorf("%s%s", , )
	}
	.errorf("unexpected %s in %s", , )
}

// recover is the handler that turns panics into returns from the top level of Parse.
func ( *Tree) ( *error) {
	 := recover()
	if  != nil {
		if ,  := .(runtime.Error);  {
			panic()
		}
		if  != nil {
			.stopParse()
		}
		* = .(error)
	}
}

// startParse initializes the parser, using the lexer.
func ( *Tree) ( []map[string]any,  *lexer,  map[string]*Tree) {
	.Root = nil
	.lex = 
	.vars = []string{"$"}
	.funcs = 
	.treeSet = 
	.options = lexOptions{
		emitComment: .Mode&ParseComments != 0,
		breakOK:     !.hasFunction("break"),
		continueOK:  !.hasFunction("continue"),
	}
}

// stopParse terminates parsing.
func ( *Tree) () {
	.lex = nil
	.vars = nil
	.funcs = nil
	.treeSet = nil
}

// Parse parses the template definition string to construct a representation of
// the template for execution. If either action delimiter string is empty, the
// default ("{{" or "}}") is used. Embedded template definitions are added to
// the treeSet map.
func ( *Tree) (, ,  string,  map[string]*Tree,  ...map[string]any) ( *Tree,  error) {
	defer .recover(&)
	.ParseName = .Name
	 := lex(.Name, , , )
	.startParse(, , )
	.text = 
	.parse()
	.add()
	.stopParse()
	return , nil
}

// add adds tree to t.treeSet.
func ( *Tree) () {
	 := .treeSet[.Name]
	if  == nil || IsEmptyTree(.Root) {
		.treeSet[.Name] = 
		return
	}
	if !IsEmptyTree(.Root) {
		.errorf("template: multiple definition of template %q", .Name)
	}
}

// IsEmptyTree reports whether this tree (node) is empty of everything but space or comments.
func ( Node) bool {
	switch n := .(type) {
	case nil:
		return true
	case *ActionNode:
	case *CommentNode:
		return true
	case *IfNode:
	case *ListNode:
		for ,  := range .Nodes {
			if !() {
				return false
			}
		}
		return true
	case *RangeNode:
	case *TemplateNode:
	case *TextNode:
		return len(bytes.TrimSpace(.Text)) == 0
	case *WithNode:
	default:
		panic("unknown node: " + .String())
	}
	return false
}

// parse is the top-level parser for a template, essentially the same
// as itemList except it also parses {{define}} actions.
// It runs to EOF.
func ( *Tree) () {
	.Root = .newList(.peek().pos)
	for .peek().typ != itemEOF {
		if .peek().typ == itemLeftDelim {
			 := .next()
			if .nextNonSpace().typ == itemDefine {
				 := New("definition") // name will be updated once we know it.
				.text = .text
				.Mode = .Mode
				.ParseName = .ParseName
				.startParse(.funcs, .lex, .treeSet)
				.parseDefinition()
				continue
			}
			.backup2()
		}
		switch  := .textOrAction(); .Type() {
		case nodeEnd, nodeElse:
			.errorf("unexpected %s", )
		default:
			.Root.append()
		}
	}
}

// parseDefinition parses a {{define}} ...  {{end}} template definition and
// installs the definition in t.treeSet. The "define" keyword has already
// been scanned.
func ( *Tree) () {
	const  = "define clause"
	 := .expectOneOf(itemString, itemRawString, )
	var  error
	.Name,  = strconv.Unquote(.val)
	if  != nil {
		.error()
	}
	.expect(itemRightDelim, )
	var  Node
	.Root,  = .itemList()
	if .Type() != nodeEnd {
		.errorf("unexpected %s in %s", , )
	}
	.add()
	.stopParse()
}

// itemList:
//
//	textOrAction*
//
// Terminates at {{end}} or {{else}}, returned separately.
func ( *Tree) () ( *ListNode,  Node) {
	 = .newList(.peekNonSpace().pos)
	for .peekNonSpace().typ != itemEOF {
		 := .textOrAction()
		switch .Type() {
		case nodeEnd, nodeElse:
			return , 
		}
		.append()
	}
	.errorf("unexpected EOF")
	return
}

// textOrAction:
//
//	text | comment | action
func ( *Tree) () Node {
	switch  := .nextNonSpace(); .typ {
	case itemText:
		return .newText(.pos, .val)
	case itemLeftDelim:
		.actionLine = .line
		defer .clearActionLine()
		return .action()
	case itemComment:
		return .newComment(.pos, .val)
	default:
		.unexpected(, "input")
	}
	return nil
}

func ( *Tree) () {
	.actionLine = 0
}

// Action:
//
//	control
//	command ("|" command)*
//
// Left delim is past. Now get actions.
// First word could be a keyword such as range.
func ( *Tree) () ( Node) {
	switch  := .nextNonSpace(); .typ {
	case itemBlock:
		return .blockControl()
	case itemBreak:
		return .breakControl(.pos, .line)
	case itemContinue:
		return .continueControl(.pos, .line)
	case itemElse:
		return .elseControl()
	case itemEnd:
		return .endControl()
	case itemIf:
		return .ifControl()
	case itemRange:
		return .rangeControl()
	case itemTemplate:
		return .templateControl()
	case itemWith:
		return .withControl()
	}
	.backup()
	 := .peek()
	// Do not pop variables; they persist until "end".
	return .newAction(.pos, .line, .pipeline("command", itemRightDelim))
}

// Break:
//
//	{{break}}
//
// Break keyword is past.
func ( *Tree) ( Pos,  int) Node {
	if  := .nextNonSpace(); .typ != itemRightDelim {
		.unexpected(, "{{break}}")
	}
	if .rangeDepth == 0 {
		.errorf("{{break}} outside {{range}}")
	}
	return .newBreak(, )
}

// Continue:
//
//	{{continue}}
//
// Continue keyword is past.
func ( *Tree) ( Pos,  int) Node {
	if  := .nextNonSpace(); .typ != itemRightDelim {
		.unexpected(, "{{continue}}")
	}
	if .rangeDepth == 0 {
		.errorf("{{continue}} outside {{range}}")
	}
	return .newContinue(, )
}

// Pipeline:
//
//	declarations? command ('|' command)*
func ( *Tree) ( string,  itemType) ( *PipeNode) {
	 := .peekNonSpace()
	 = .newPipeline(.pos, .line, nil)
	// Are there declarations or assignments?
:
	if  := .peekNonSpace(); .typ == itemVariable {
		.next()
		// Since space is a token, we need 3-token look-ahead here in the worst case:
		// in "$x foo" we need to read "foo" (as opposed to ":=") to know that $x is an
		// argument variable rather than a declaration. So remember the token
		// adjacent to the variable so we can push it back if necessary.
		 := .peek()
		 := .peekNonSpace()
		switch {
		case .typ == itemAssign, .typ == itemDeclare:
			.IsAssign = .typ == itemAssign
			.nextNonSpace()
			.Decl = append(.Decl, .newVariable(.pos, .val))
			.vars = append(.vars, .val)
		case .typ == itemChar && .val == ",":
			.nextNonSpace()
			.Decl = append(.Decl, .newVariable(.pos, .val))
			.vars = append(.vars, .val)
			if  == "range" && len(.Decl) < 2 {
				switch .peekNonSpace().typ {
				case itemVariable, itemRightDelim, itemRightParen:
					// second initialized variable in a range pipeline
					goto 
				default:
					.errorf("range can only initialize variables")
				}
			}
			.errorf("too many declarations in %s", )
		case .typ == itemSpace:
			.backup3(, )
		default:
			.backup2()
		}
	}
	for {
		switch  := .nextNonSpace(); .typ {
		case :
			// At this point, the pipeline is complete
			.checkPipeline(, )
			return
		case itemBool, itemCharConstant, itemComplex, itemDot, itemField, itemIdentifier,
			itemNumber, itemNil, itemRawString, itemString, itemVariable, itemLeftParen:
			.backup()
			.append(.command())
		default:
			.unexpected(, )
		}
	}
}

func ( *Tree) ( *PipeNode,  string) {
	// Reject empty pipelines
	if len(.Cmds) == 0 {
		.errorf("missing value for %s", )
	}
	// Only the first command of a pipeline can start with a non executable operand
	for ,  := range .Cmds[1:] {
		switch .Args[0].Type() {
		case NodeBool, NodeDot, NodeNil, NodeNumber, NodeString:
			// With A|B|C, pipeline stage 2 is B
			.errorf("non executable command in pipeline stage %d", +2)
		}
	}
}

func ( *Tree) ( string) ( Pos,  int,  *PipeNode, ,  *ListNode) {
	defer .popVars(len(.vars))
	 = .pipeline(, itemRightDelim)
	if  == "range" {
		.rangeDepth++
	}
	var  Node
	,  = .itemList()
	if  == "range" {
		.rangeDepth--
	}
	switch .Type() {
	case nodeEnd: //done
	case nodeElse:
		// Special case for "else if" and "else with".
		// If the "else" is followed immediately by an "if" or "with",
		// the elseControl will have left the "if" or "with" token pending. Treat
		//	{{if a}}_{{else if b}}_{{end}}
		//  {{with a}}_{{else with b}}_{{end}}
		// as
		//	{{if a}}_{{else}}{{if b}}_{{end}}{{end}}
		//  {{with a}}_{{else}}{{with b}}_{{end}}{{end}}.
		// To do this, parse the "if" or "with" as usual and stop at it {{end}};
		// the subsequent{{end}} is assumed. This technique works even for long if-else-if chains.
		if  == "if" && .peek().typ == itemIf {
			.next() // Consume the "if" token.
			 = .newList(.Position())
			.append(.ifControl())
		} else if  == "with" && .peek().typ == itemWith {
			.next()
			 = .newList(.Position())
			.append(.withControl())
		} else {
			,  = .itemList()
			if .Type() != nodeEnd {
				.errorf("expected end; found %s", )
			}
		}
	}
	return .Position(), .Line, , , 
}

// If:
//
//	{{if pipeline}} itemList {{end}}
//	{{if pipeline}} itemList {{else}} itemList {{end}}
//
// If keyword is past.
func ( *Tree) () Node {
	return .newIf(.parseControl("if"))
}

// Range:
//
//	{{range pipeline}} itemList {{end}}
//	{{range pipeline}} itemList {{else}} itemList {{end}}
//
// Range keyword is past.
func ( *Tree) () Node {
	 := .newRange(.parseControl("range"))
	return 
}

// With:
//
//	{{with pipeline}} itemList {{end}}
//	{{with pipeline}} itemList {{else}} itemList {{end}}
//
// If keyword is past.
func ( *Tree) () Node {
	return .newWith(.parseControl("with"))
}

// End:
//
//	{{end}}
//
// End keyword is past.
func ( *Tree) () Node {
	return .newEnd(.expect(itemRightDelim, "end").pos)
}

// Else:
//
//	{{else}}
//
// Else keyword is past.
func ( *Tree) () Node {
	 := .peekNonSpace()
	// The "{{else if ... " and "{{else with ..." will be
	// treated as "{{else}}{{if ..." and "{{else}}{{with ...".
	// So return the else node here.
	if .typ == itemIf || .typ == itemWith {
		return .newElse(.pos, .line)
	}
	 := .expect(itemRightDelim, "else")
	return .newElse(.pos, .line)
}

// Block:
//
//	{{block stringValue pipeline}}
//
// Block keyword is past.
// The name must be something that can evaluate to a string.
// The pipeline is mandatory.
func ( *Tree) () Node {
	const  = "block clause"

	 := .nextNonSpace()
	 := .parseTemplateName(, )
	 := .pipeline(, itemRightDelim)

	 := New() // name will be updated once we know it.
	.text = .text
	.Mode = .Mode
	.ParseName = .ParseName
	.startParse(.funcs, .lex, .treeSet)
	var  Node
	.Root,  = .itemList()
	if .Type() != nodeEnd {
		.errorf("unexpected %s in %s", , )
	}
	.add()
	.stopParse()

	return .newTemplate(.pos, .line, , )
}

// Template:
//
//	{{template stringValue pipeline}}
//
// Template keyword is past. The name must be something that can evaluate
// to a string.
func ( *Tree) () Node {
	const  = "template clause"
	 := .nextNonSpace()
	 := .parseTemplateName(, )
	var  *PipeNode
	if .nextNonSpace().typ != itemRightDelim {
		.backup()
		// Do not pop variables; they persist until "end".
		 = .pipeline(, itemRightDelim)
	}
	return .newTemplate(.pos, .line, , )
}

func ( *Tree) ( item,  string) ( string) {
	switch .typ {
	case itemString, itemRawString:
		,  := strconv.Unquote(.val)
		if  != nil {
			.error()
		}
		 = 
	default:
		.unexpected(, )
	}
	return
}

// command:
//
//	operand (space operand)*
//
// space-separated arguments up to a pipeline character or right delimiter.
// we consume the pipe character but leave the right delim to terminate the action.
func ( *Tree) () *CommandNode {
	 := .newCommand(.peekNonSpace().pos)
	for {
		.peekNonSpace() // skip leading spaces.
		 := .operand()
		if  != nil {
			.append()
		}
		switch  := .next(); .typ {
		case itemSpace:
			continue
		case itemRightDelim, itemRightParen:
			.backup()
		case itemPipe:
			// nothing here; break loop below
		default:
			.unexpected(, "operand")
		}
		break
	}
	if len(.Args) == 0 {
		.errorf("empty command")
	}
	return 
}

// operand:
//
//	term .Field*
//
// An operand is a space-separated component of a command,
// a term possibly followed by field accesses.
// A nil return means the next item is not an operand.
func ( *Tree) () Node {
	 := .term()
	if  == nil {
		return nil
	}
	if .peek().typ == itemField {
		 := .newChain(.peek().pos, )
		for .peek().typ == itemField {
			.Add(.next().val)
		}
		// Compatibility with original API: If the term is of type NodeField
		// or NodeVariable, just put more fields on the original.
		// Otherwise, keep the Chain node.
		// Obvious parsing errors involving literal values are detected here.
		// More complex error cases will have to be handled at execution time.
		switch .Type() {
		case NodeField:
			 = .newField(.Position(), .String())
		case NodeVariable:
			 = .newVariable(.Position(), .String())
		case NodeBool, NodeString, NodeNumber, NodeNil, NodeDot:
			.errorf("unexpected . after term %q", .String())
		default:
			 = 
		}
	}
	return 
}

// term:
//
//	literal (number, string, nil, boolean)
//	function (identifier)
//	.
//	.Field
//	$
//	'(' pipeline ')'
//
// A term is a simple "expression".
// A nil return means the next item is not a term.
func ( *Tree) () Node {
	switch  := .nextNonSpace(); .typ {
	case itemIdentifier:
		 := .Mode&SkipFuncCheck == 0
		if  && !.hasFunction(.val) {
			.errorf("function %q not defined", .val)
		}
		return NewIdentifier(.val).SetTree().SetPos(.pos)
	case itemDot:
		return .newDot(.pos)
	case itemNil:
		return .newNil(.pos)
	case itemVariable:
		return .useVar(.pos, .val)
	case itemField:
		return .newField(.pos, .val)
	case itemBool:
		return .newBool(.pos, .val == "true")
	case itemCharConstant, itemComplex, itemNumber:
		,  := .newNumber(.pos, .val, .typ)
		if  != nil {
			.error()
		}
		return 
	case itemLeftParen:
		return .pipeline("parenthesized pipeline", itemRightParen)
	case itemString, itemRawString:
		,  := strconv.Unquote(.val)
		if  != nil {
			.error()
		}
		return .newString(.pos, .val, )
	}
	.backup()
	return nil
}

// hasFunction reports if a function name exists in the Tree's maps.
func ( *Tree) ( string) bool {
	for ,  := range .funcs {
		if  == nil {
			continue
		}
		if [] != nil {
			return true
		}
	}
	return false
}

// popVars trims the variable list to the specified length
func ( *Tree) ( int) {
	.vars = .vars[:]
}

// useVar returns a node for a variable reference. It errors if the
// variable is not defined.
func ( *Tree) ( Pos,  string) Node {
	 := .newVariable(, )
	for ,  := range .vars {
		if  == .Ident[0] {
			return 
		}
	}
	.errorf("undefined variable %q", .Ident[0])
	return nil
}