// Copyright 2010 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 html

import (

	"errors"

	"fmt"

	"io"

	"strings"

	a "golang.org/x/net/html/atom"

)

// A parser implements the HTML5 parsing algorithm:

// https://html.spec.whatwg.org/multipage/syntax.html#tree-construction

type parser struct {

	// tokenizer provides the tokens for the parser.

	tokenizer *Tokenizer

	// tok is the most recently read token.

	tok Token

	// Self-closing tags like <hr/> are treated as start tags, except that

	// hasSelfClosingToken is set while they are being processed.

	hasSelfClosingToken bool

	// doc is the document root element.

	doc *Node

	// The stack of open elements (section 12.2.4.2) and active formatting

	// elements (section 12.2.4.3).

	oe, afe nodeStack

	// Element pointers (section 12.2.4.4).

	head, form *Node

	// Other parsing state flags (section 12.2.4.5).

	scripting, framesetOK bool

	// The stack of template insertion modes

	templateStack insertionModeStack

	// im is the current insertion mode.

	im insertionMode

	// originalIM is the insertion mode to go back to after completing a text

	// or inTableText insertion mode.

	originalIM insertionMode

	// fosterParenting is whether new elements should be inserted according to

	// the foster parenting rules (section 12.2.6.1).

	fosterParenting bool

	// quirks is whether the parser is operating in "quirks mode."

	quirks bool

	// fragment is whether the parser is parsing an HTML fragment.

	fragment bool

	// context is the context element when parsing an HTML fragment

	// (section 12.4).

	context *Node

}

func (p *parser) top() *Node {

	if n := p.oe.top(); n != nil {

		return n

	}

	return p.doc

}

// Stop tags for use in popUntil. These come from section 12.2.4.2.

var (

	defaultScopeStopTags = map[string][]a.Atom{

		"":     {a.Applet, a.Caption, a.Html, a.Table, a.Td, a.Th, a.Marquee, a.Object, a.Template},

		"math": {a.AnnotationXml, a.Mi, a.Mn, a.Mo, a.Ms, a.Mtext},

		"svg":  {a.Desc, a.ForeignObject, a.Title},

	}

)

type scope int

const (

	defaultScope scope = iota

	listItemScope

	buttonScope

	tableScope

	tableRowScope

	tableBodyScope

	selectScope

)

// popUntil pops the stack of open elements at the highest element whose tag

// is in matchTags, provided there is no higher element in the scope's stop

// tags (as defined in section 12.2.4.2). It returns whether or not there was

// such an element. If there was not, popUntil leaves the stack unchanged.

//

// For example, the set of stop tags for table scope is: "html", "table". If

// the stack was:

// ["html", "body", "font", "table", "b", "i", "u"]

// then popUntil(tableScope, "font") would return false, but

// popUntil(tableScope, "i") would return true and the stack would become:

// ["html", "body", "font", "table", "b"]

//

// If an element's tag is in both the stop tags and matchTags, then the stack

// will be popped and the function returns true (provided, of course, there was

// no higher element in the stack that was also in the stop tags). For example,

// popUntil(tableScope, "table") returns true and leaves:

// ["html", "body", "font"]

func (p *parser) popUntil(s scope, matchTags ...a.Atom) bool {

	if i := p.indexOfElementInScope(s, matchTags...); i != -1 {

		p.oe = p.oe[:i]

		return true

	}

	return false

}

// indexOfElementInScope returns the index in p.oe of the highest element whose

// tag is in matchTags that is in scope. If no matching element is in scope, it

// returns -1.

func (p *parser) indexOfElementInScope(s scope, matchTags ...a.Atom) int {

	for i := len(p.oe) - 1; i >= 0; i-- {

		tagAtom := p.oe[i].DataAtom

		if p.oe[i].Namespace == "" {

			for _, t := range matchTags {

				if t == tagAtom {

					return i

				}

			}

			switch s {

			case defaultScope:

				// No-op.

			case listItemScope:

				if tagAtom == a.Ol || tagAtom == a.Ul {

					return -1

				}

			case buttonScope:

				if tagAtom == a.Button {

					return -1

				}

			case tableScope:

				if tagAtom == a.Html || tagAtom == a.Table || tagAtom == a.Template {

					return -1

				}

			case selectScope:

				if tagAtom != a.Optgroup && tagAtom != a.Option {

					return -1

				}

			default:

				panic("unreachable")

			}

		}

		switch s {

		case defaultScope, listItemScope, buttonScope:

			for _, t := range defaultScopeStopTags[p.oe[i].Namespace] {

				if t == tagAtom {

					return -1

				}

			}

		}

	}

	return -1

}

// elementInScope is like popUntil, except that it doesn't modify the stack of

// open elements.

func (p *parser) elementInScope(s scope, matchTags ...a.Atom) bool {

	return p.indexOfElementInScope(s, matchTags...) != -1

}

// clearStackToContext pops elements off the stack of open elements until a

// scope-defined element is found.

func (p *parser) clearStackToContext(s scope) {

	for i := len(p.oe) - 1; i >= 0; i-- {

		tagAtom := p.oe[i].DataAtom

		switch s {

		case tableScope:

			if tagAtom == a.Html || tagAtom == a.Table || tagAtom == a.Template {

				p.oe = p.oe[:i+1]

				return

			}

		case tableRowScope:

			if tagAtom == a.Html || tagAtom == a.Tr || tagAtom == a.Template {

				p.oe = p.oe[:i+1]

				return

			}

		case tableBodyScope:

			if tagAtom == a.Html || tagAtom == a.Tbody || tagAtom == a.Tfoot || tagAtom == a.Thead || tagAtom == a.Template {

				p.oe = p.oe[:i+1]

				return

			}

		default:

			panic("unreachable")

		}

	}

}

// generateImpliedEndTags pops nodes off the stack of open elements as long as

// the top node has a tag name of dd, dt, li, optgroup, option, p, rb, rp, rt or rtc.

// If exceptions are specified, nodes with that name will not be popped off.

func (p *parser) generateImpliedEndTags(exceptions ...string) {

	var i int

loop:

	for i = len(p.oe) - 1; i >= 0; i-- {

		n := p.oe[i]

		if n.Type == ElementNode {

			switch n.DataAtom {

			case a.Dd, a.Dt, a.Li, a.Optgroup, a.Option, a.P, a.Rb, a.Rp, a.Rt, a.Rtc:

				for _, except := range exceptions {

					if n.Data == except {

						break loop

					}

				}

				continue

			}

		}

		break

	}

	p.oe = p.oe[:i+1]

}

// addChild adds a child node n to the top element, and pushes n onto the stack

// of open elements if it is an element node.

func (p *parser) addChild(n *Node) {

	if p.shouldFosterParent() {

		p.fosterParent(n)

	} else {

		p.top().AppendChild(n)

	}

	if n.Type == ElementNode {

		p.oe = append(p.oe, n)

	}

}

// shouldFosterParent returns whether the next node to be added should be

// foster parented.

func (p *parser) shouldFosterParent() bool {

	if p.fosterParenting {

		switch p.top().DataAtom {

		case a.Table, a.Tbody, a.Tfoot, a.Thead, a.Tr:

			return true

		}

	}

	return false

}

// fosterParent adds a child node according to the foster parenting rules.

// Section 12.2.6.1, "foster parenting".

func (p *parser) fosterParent(n *Node) {

	var table, parent, prev, template *Node

	var i int

	for i = len(p.oe) - 1; i >= 0; i-- {

		if p.oe[i].DataAtom == a.Table {

			table = p.oe[i]

			break

		}

	}

	var j int

	for j = len(p.oe) - 1; j >= 0; j-- {

		if p.oe[j].DataAtom == a.Template {

			template = p.oe[j]

			break

		}

	}

	if template != nil && (table == nil || j > i) {

		template.AppendChild(n)

		return

	}

	if table == nil {

		// The foster parent is the html element.

		parent = p.oe[0]

	} else {

		parent = table.Parent

	}

	if parent == nil {

		parent = p.oe[i-1]

	}

	if table != nil {

		prev = table.PrevSibling

	} else {

		prev = parent.LastChild

	}

	if prev != nil && prev.Type == TextNode && n.Type == TextNode {

		prev.Data += n.Data

		return

	}

	parent.InsertBefore(n, table)

}

// addText adds text to the preceding node if it is a text node, or else it

// calls addChild with a new text node.

func (p *parser) addText(text string) {

	if text == "" {

		return

	}

	if p.shouldFosterParent() {

		p.fosterParent(&Node{

			Type: TextNode,

			Data: text,

		})

		return

	}

	t := p.top()

	if n := t.LastChild; n != nil && n.Type == TextNode {

		n.Data += text

		return

	}

	p.addChild(&Node{

		Type: TextNode,

		Data: text,

	})

}

// addElement adds a child element based on the current token.

func (p *parser) addElement() {

	p.addChild(&Node{

		Type:     ElementNode,

		DataAtom: p.tok.DataAtom,

		Data:     p.tok.Data,

		Attr:     p.tok.Attr,

	})

}

// Section 12.2.4.3.

func (p *parser) addFormattingElement() {

	tagAtom, attr := p.tok.DataAtom, p.tok.Attr

	p.addElement()

	// Implement the Noah's Ark clause, but with three per family instead of two.

	identicalElements := 0

findIdenticalElements:

	for i := len(p.afe) - 1; i >= 0; i-- {

		n := p.afe[i]

		if n.Type == scopeMarkerNode {

			break

		}

		if n.Type != ElementNode {

			continue

		}

		if n.Namespace != "" {

			continue

		}

		if n.DataAtom != tagAtom {

			continue

		}

		if len(n.Attr) != len(attr) {

			continue

		}

	compareAttributes:

		for _, t0 := range n.Attr {

			for _, t1 := range attr {

				if t0.Key == t1.Key && t0.Namespace == t1.Namespace && t0.Val == t1.Val {

					// Found a match for this attribute, continue with the next attribute.

					continue compareAttributes

				}

			}

			// If we get here, there is no attribute that matches a.

			// Therefore the element is not identical to the new one.

			continue findIdenticalElements

		}

		identicalElements++

		if identicalElements >= 3 {

			p.afe.remove(n)

		}

	}

	p.afe = append(p.afe, p.top())

}

// Section 12.2.4.3.

func (p *parser) clearActiveFormattingElements() {

	for {

		n := p.afe.pop()

		if len(p.afe) == 0 || n.Type == scopeMarkerNode {

			return

		}

	}

}

// Section 12.2.4.3.

func (p *parser) reconstructActiveFormattingElements() {

	n := p.afe.top()

	if n == nil {

		return

	}

	if n.Type == scopeMarkerNode || p.oe.index(n) != -1 {

		return

	}

	i := len(p.afe) - 1

	for n.Type != scopeMarkerNode && p.oe.index(n) == -1 {

		if i == 0 {

			i = -1

			break

		}

		i--

		n = p.afe[i]

	}

	for {

		i++

		clone := p.afe[i].clone()

		p.addChild(clone)

		p.afe[i] = clone

		if i == len(p.afe)-1 {

			break

		}

	}

}

// Section 12.2.5.

func (p *parser) acknowledgeSelfClosingTag() {

	p.hasSelfClosingToken = false

}

// An insertion mode (section 12.2.4.1) is the state transition function from