src/pkg/html/parse.go - go - Git at Google

 // 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 (
 	"io"
 	"os"
 )

 // A NodeType is the type of a Node.
 type NodeType int

 const (
 	ErrorNode NodeType = iota
 	TextNode
 	DocumentNode
 	ElementNode
 	CommentNode
 )

 // A Node consists of a NodeType and some Data (tag name for element nodes,
 // content for text) and are part of a tree of Nodes. Element nodes may also
 // contain a slice of Attributes. Data is unescaped, so that it looks like
 // "a<b" rather than "a&lt;b".
 type Node struct {
 	Parent *Node
 	Child  []*Node
 	Type   NodeType
 	Data   string
 	Attr   []Attribute
 }

 // A parser implements the HTML5 parsing algorithm:
 // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.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 re-interpreted as a two-token sequence:
 	// <hr> followed by </hr>. hasSelfClosingToken is true if we have just read
 	// the synthetic start tag and the next one due is the matching end tag.
 	hasSelfClosingToken bool
 	// doc is the document root element.
 	doc *Node
 	// The stack of open elements (section 10.2.3.2).
 	stack []*Node
 	// Element pointers (section 10.2.3.4).
 	head, form *Node
 	// Other parsing state flags (section 10.2.3.5).
 	scripting, framesetOK bool
 }

 // push pushes onto the stack of open elements.
 func (p *parser) push(n *Node) {
 	p.stack = append(p.stack, n)
 }

 // top returns the top of the stack of open elements.
 // This is also known as the current node.
 func (p *parser) top() *Node {
 	if n := len(p.stack); n > 0 {
 		return p.stack[n-1]
 	}
 	return p.doc
 }

 // pop pops the top of the stack of open elements.
 // It will panic if the stack is empty.
 func (p *parser) pop() *Node {
 	n := len(p.stack)
 	ret := p.stack[n-1]
 	p.stack = p.stack[:n-1]
 	return ret
 }

 // stopTags for use in popUntil. These come from section 10.2.3.2.
 var (
 	defaultScopeStopTags  = []string{"applet", "caption", "html", "table", "td", "th", "marquee", "object"}
 	listItemScopeStopTags = []string{"applet", "caption", "html", "table", "td", "th", "marquee", "object", "ol", "ul"}
 	buttonScopeStopTags   = []string{"applet", "caption", "html", "table", "td", "th", "marquee", "object", "button"}
 	tableScopeStopTags    = []string{"html", "table"}
 )

 // popUntil pops the stack of open elements at the highest element whose tag
 // is in matchTags, provided there is no higher element in stopTags. It returns
 // whether or not there was such an element. If there was not, popUntil leaves
 // the stack unchanged.
 //
 // For example, if the stack was:
 // ["html", "body", "font", "table", "b", "i", "u"]
 // then popUntil([]string{"html, "table"}, "font") would return false, but
 // popUntil([]string{"html, "table"}, "i") would return true and the resultant
 // stack would be:
 // ["html", "body", "font", "table", "b"]
 //
 // If an element's tag is in both stopTags 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 stopTags). For example,
 // popUntil([]string{"html, "table"}, "table") would return true and leave:
 // ["html", "body", "font"]
 func (p *parser) popUntil(stopTags []string, matchTags ...string) bool {
 	for i := len(p.stack) - 1; i >= 0; i-- {
 		tag := p.stack[i].Data
 		for _, t := range matchTags {
 			if t == tag {
 				p.stack = p.stack[:i]
 				return true
 			}
 		}
 		for _, t := range stopTags {
 			if t == tag {
 				return false
 			}
 		}
 	}
 	return false
 }

 // addChild adds a child node n to the top element, and pushes n if it is an
 // element node (text nodes are not part of the stack of open elements).
 func (p *parser) addChild(n *Node) {
 	m := p.top()
 	m.Child = append(m.Child, n)
 	if n.Type == ElementNode {
 		p.push(n)
 	}
 }

 // addText calls addChild with a text node.
 func (p *parser) addText(text string) {
 	// TODO: merge s with previous text, if the preceding node is a text node.
 	// TODO: distinguish whitespace text from others.
 	p.addChild(&Node{
 		Type: TextNode,
 		Data: text,
 	})
 }

 // addElement calls addChild with an element node.
 func (p *parser) addElement(tag string, attr []Attribute) {
 	p.addChild(&Node{
 		Type: ElementNode,
 		Data: tag,
 		Attr: attr,
 	})
 }

 // Section 10.2.3.3.
 func (p *parser) addFormattingElement(tag string, attr []Attribute) {
 	p.addElement(tag, attr)
 	// TODO.
 }

 // Section 10.2.3.3.
 func (p *parser) reconstructActiveFormattingElements() {
 	// TODO.
 }

 // read reads the next token. This is usually from the tokenizer, but it may
 // be the synthesized end tag implied by a self-closing tag.
 func (p *parser) read() os.Error {
 	if p.hasSelfClosingToken {
 		p.hasSelfClosingToken = false
 		p.tok.Type = EndTagToken
 		p.tok.Attr = nil
 		return nil
 	}
 	p.tokenizer.Next()
 	p.tok = p.tokenizer.Token()
 	switch p.tok.Type {
 	case ErrorToken:
 		return p.tokenizer.Error()
 	case SelfClosingTagToken:
 		p.hasSelfClosingToken = true
 		p.tok.Type = StartTagToken
 	}
 	return nil
 }

 // Section 10.2.4.
 func (p *parser) acknowledgeSelfClosingTag() {
 	p.hasSelfClosingToken = false
 }

 // An insertion mode (section 10.2.3.1) is the state transition function from
 // a particular state in the HTML5 parser's state machine. It updates the
 // parser's fields depending on parser.token (where ErrorToken means EOF). In
 // addition to returning the next insertionMode state, it also returns whether
 // the token was consumed.
 type insertionMode func(*parser) (insertionMode, bool)

 // useTheRulesFor runs the delegate insertionMode over p, returning the actual
 // insertionMode unless the delegate caused a state transition.
 // Section 10.2.3.1, "using the rules for".
 func useTheRulesFor(p *parser, actual, delegate insertionMode) (insertionMode, bool) {
 	im, consumed := delegate(p)
 	if im != delegate {
 		return im, consumed
 	}
 	return actual, consumed
 }

 // Section 10.2.5.4.
 func initialIM(p *parser) (insertionMode, bool) {
 	// TODO: check p.tok for DOCTYPE.
 	return beforeHTMLIM, false
 }

 // Section 10.2.5.5.
 func beforeHTMLIM(p *parser) (insertionMode, bool) {
 	var (
 		add     bool
 		attr    []Attribute
 		implied bool
 	)
 	switch p.tok.Type {
 	case ErrorToken:
 		implied = true
 	case TextToken:
 		// TODO: distinguish whitespace text from others.
 		implied = true
 	case StartTagToken:
 		if p.tok.Data == "html" {
 			add = true
 			attr = p.tok.Attr
 		} else {
 			implied = true
 		}
 	case EndTagToken:
 		switch p.tok.Data {
 		case "head", "body", "html", "br":
 			implied = true
 		default:
 			// Ignore the token.
 		}
 	}
 	if add || implied {
 		p.addElement("html", attr)
 	}
 	return beforeHeadIM, !implied
 }

 // Section 10.2.5.6.
 func beforeHeadIM(p *parser) (insertionMode, bool) {
 	var (
 		add     bool
 		attr    []Attribute
 		implied bool
 	)
 	switch p.tok.Type {
 	case ErrorToken:
 		implied = true
 	case TextToken:
 		// TODO: distinguish whitespace text from others.
 		implied = true
 	case StartTagToken:
 		switch p.tok.Data {
 		case "head":
 			add = true
 			attr = p.tok.Attr
 		case "html":
 			return useTheRulesFor(p, beforeHeadIM, inBodyIM)
 		default:
 			implied = true
 		}
 	case EndTagToken:
 		switch p.tok.Data {
 		case "head", "body", "html", "br":
 			implied = true
 		default:
 			// Ignore the token.
 		}
 	}
 	if add || implied {
 		p.addElement("head", attr)
 	}
 	return inHeadIM, !implied
 }

 // Section 10.2.5.7.
 func inHeadIM(p *parser) (insertionMode, bool) {
 	var (
 		pop     bool
 		implied bool
 	)
 	switch p.tok.Type {
 	case ErrorToken, TextToken:
 		implied = true
 	case StartTagToken:
 		switch p.tok.Data {
 		case "meta":
 			// TODO.
 		case "script":
 			// TODO.
 		default:
 			implied = true
 		}
 	case EndTagToken:
 		if p.tok.Data == "head" {
 			pop = true
 		}
 		// TODO.
 	}
 	if pop || implied {
 		n := p.pop()
 		if n.Data != "head" {
 			panic("html: bad parser state")
 		}
 		return afterHeadIM, !implied
 	}
 	return inHeadIM, !implied
 }

 // Section 10.2.5.9.
 func afterHeadIM(p *parser) (insertionMode, bool) {
 	var (
 		add        bool
 		attr       []Attribute
 		framesetOK bool
 		implied    bool
 	)
 	switch p.tok.Type {
 	case ErrorToken, TextToken:
 		implied = true
 		framesetOK = true
 	case StartTagToken:
 		switch p.tok.Data {
 		case "html":
 			// TODO.
 		case "body":
 			add = true
 			attr = p.tok.Attr
 			framesetOK = false
 		case "frameset":
 			// TODO.
 		case "base", "basefont", "bgsound", "link", "meta", "noframes", "script", "style", "title":
 			// TODO.
 		case "head":
 			// TODO.
 		default:
 			implied = true
 			framesetOK = true
 		}
 	case EndTagToken:
 		// TODO.
 	}
 	if add || implied {
 		p.addElement("body", attr)
 		p.framesetOK = framesetOK
 	}
 	return inBodyIM, !implied
 }

 // Section 10.2.5.10.
 func inBodyIM(p *parser) (insertionMode, bool) {
 	var endP bool
 	switch p.tok.Type {
 	case TextToken:
 		p.addText(p.tok.Data)
 		p.framesetOK = false
 	case StartTagToken:
 		switch p.tok.Data {
 		case "address", "article", "aside", "blockquote", "center", "details", "dir", "div", "dl", "fieldset", "figcaption", "figure", "footer", "header", "hgroup", "menu", "nav", "ol", "p", "section", "summary", "ul":
 			// TODO: Do the proper "does the stack of open elements has a p element in button scope" algorithm in section 10.2.3.2.
 			n := p.top()
 			if n.Type == ElementNode && n.Data == "p" {
 				endP = true
 			} else {
 				p.addElement(p.tok.Data, p.tok.Attr)
 			}
 		case "h1", "h2", "h3", "h4", "h5", "h6":
 			// TODO: auto-insert </p> if necessary.
 			switch n := p.top(); n.Data {
 			case "h1", "h2", "h3", "h4", "h5", "h6":
 				p.pop()
 			}
 			p.addElement(p.tok.Data, p.tok.Attr)
 		case "b", "big", "code", "em", "font", "i", "s", "small", "strike", "strong", "tt", "u":
 			p.reconstructActiveFormattingElements()
 			p.addFormattingElement(p.tok.Data, p.tok.Attr)
 		case "area", "br", "embed", "img", "input", "keygen", "wbr":
 			p.reconstructActiveFormattingElements()
 			p.addElement(p.tok.Data, p.tok.Attr)
 			p.pop()
 			p.acknowledgeSelfClosingTag()
 			p.framesetOK = false
 		case "table":
 			// TODO: auto-insert </p> if necessary, depending on quirks mode.
 			p.addElement(p.tok.Data, p.tok.Attr)
 			p.framesetOK = false
 			return inTableIM, true
 		case "hr":
 			// TODO: auto-insert </p> if necessary.
 			p.addElement(p.tok.Data, p.tok.Attr)
 			p.pop()
 			p.acknowledgeSelfClosingTag()
 			p.framesetOK = false
 		default:
 			// TODO.
 		}
 	case EndTagToken:
 		switch p.tok.Data {
 		case "body":
 			// TODO: autoclose the stack of open elements.
 			return afterBodyIM, true
 		case "a", "b", "big", "code", "em", "font", "i", "nobr", "s", "small", "strike", "strong", "tt", "u":
 			// TODO: implement the "adoption agency" algorithm:
 			// http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#adoptionAgency
 			if p.tok.Data == p.top().Data {
 				p.pop()
 			}
 		default:
 			// TODO.
 		}
 	}
 	if endP {
 		// TODO: do the proper algorithm.
 		n := p.pop()
 		if n.Type != ElementNode || n.Data != "p" {
 			panic("unreachable")
 		}
 	}
 	return inBodyIM, !endP
 }

 // Section 10.2.5.12.
 func inTableIM(p *parser) (insertionMode, bool) {
 	var (
 		add      bool
 		data     string
 		attr     []Attribute
 		consumed bool
 	)
 	switch p.tok.Type {
 	case ErrorToken:
 		// Stop parsing.
 		return nil, true
 	case TextToken:
 		// TODO.
 	case StartTagToken:
 		switch p.tok.Data {
 		case "tbody", "tfoot", "thead":
 			add = true
 			data = p.tok.Data
 			attr = p.tok.Attr
 			consumed = true
 		case "td", "th", "tr":
 			add = true
 			data = "tbody"
 		default:
 			// TODO.
 		}
 	case EndTagToken:
 		switch p.tok.Data {
 		case "table":
 			if p.popUntil(tableScopeStopTags, "table") {
 				// TODO: "reset the insertion mode appropriately" as per 10.2.3.1.
 				return inBodyIM, false
 			}
 			// Ignore the token.
 			return inTableIM, true
 		case "body", "caption", "col", "colgroup", "html", "tbody", "td", "tfoot", "th", "thead", "tr":
 			// Ignore the token.
 			return inTableIM, true
 		}
 	}
 	if add {
 		// TODO: clear the stack back to a table context.
 		p.addElement(data, attr)
 		return inTableBodyIM, consumed
 	}
 	// TODO: return useTheRulesFor(inTableIM, inBodyIM, p) unless etc. etc. foster parenting.
 	return inTableIM, true
 }

 // Section 10.2.5.16.
 func inTableBodyIM(p *parser) (insertionMode, bool) {
 	var (
 		add      bool
 		data     string
 		attr     []Attribute
 		consumed bool
 	)
 	switch p.tok.Type {
 	case ErrorToken:
 		// TODO.
 	case TextToken:
 		// TODO.
 	case StartTagToken:
 		switch p.tok.Data {
 		case "tr":
 			add = true
 			data = p.tok.Data
 			attr = p.tok.Attr
 			consumed = true
 		case "td", "th":
 			add = true
 			data = "tr"
 			consumed = false
 		default:
 			// TODO.
 		}
 	case EndTagToken:
 		switch p.tok.Data {
 		case "table":
 			if p.popUntil(tableScopeStopTags, "tbody", "thead", "tfoot") {
 				return inTableIM, false
 			}
 			// Ignore the token.
 			return inTableBodyIM, true
 		case "body", "caption", "col", "colgroup", "html", "td", "th", "tr":
 			// Ignore the token.
 			return inTableBodyIM, true
 		}
 	}
 	if add {
 		// TODO: clear the stack back to a table body context.
 		p.addElement(data, attr)
 		return inRowIM, consumed
 	}
 	return useTheRulesFor(p, inTableBodyIM, inTableIM)
 }

 // Section 10.2.5.17.
 func inRowIM(p *parser) (insertionMode, bool) {
 	switch p.tok.Type {
 	case ErrorToken:
 		// TODO.
 	case TextToken:
 		// TODO.
 	case StartTagToken:
 		switch p.tok.Data {
 		case "td", "th":
 			// TODO: clear the stack back to a table row context.
 			p.addElement(p.tok.Data, p.tok.Attr)
 			// TODO: insert a marker at the end of the list of active formatting elements.
 			return inCellIM, true
 		default:
 			// TODO.
 		}
 	case EndTagToken:
 		switch p.tok.Data {
 		case "tr":
 			// TODO.
 		case "table":
 			if p.popUntil(tableScopeStopTags, "tr") {
 				return inTableBodyIM, false
 			}
 			// Ignore the token.
 			return inRowIM, true
 		case "tbody", "tfoot", "thead":
 			// TODO.
 		case "body", "caption", "col", "colgroup", "html", "td", "th":
 			// Ignore the token.
 			return inRowIM, true
 		default:
 			// TODO.
 		}
 	}
 	return useTheRulesFor(p, inRowIM, inTableIM)
 }

 // Section 10.2.5.18.
 func inCellIM(p *parser) (insertionMode, bool) {
 	var (
 		closeTheCellAndReprocess bool
 	)
 	switch p.tok.Type {
 	case StartTagToken:
 		switch p.tok.Data {
 		case "caption", "col", "colgroup", "tbody", "td", "tfoot", "th", "thead", "tr":
 			// TODO: check for "td" or "th" in table scope.
 			closeTheCellAndReprocess = true
 		}
 	case EndTagToken:
 		switch p.tok.Data {
 		case "td", "th":
 			// TODO.
 		case "body", "caption", "col", "colgroup", "html":
 			// TODO.
 		case "table", "tbody", "tfoot", "thead", "tr":
 			// TODO: check for matching element in table scope.
 			closeTheCellAndReprocess = true
 		}
 	}
 	if closeTheCellAndReprocess {
 		if p.popUntil(tableScopeStopTags, "td") || p.popUntil(tableScopeStopTags, "th") {
 			// TODO: clear the list of active formatting elements up to the last marker.
 			return inRowIM, false
 		}
 	}
 	return useTheRulesFor(p, inCellIM, inBodyIM)
 }

 // Section 10.2.5.22.
 func afterBodyIM(p *parser) (insertionMode, bool) {
 	switch p.tok.Type {
 	case ErrorToken:
 		// TODO.
 	case TextToken:
 		// TODO.
 	case StartTagToken:
 		// TODO.
 	case EndTagToken:
 		switch p.tok.Data {
 		case "html":
 			// TODO: autoclose the stack of open elements.
 			return afterAfterBodyIM, true
 		default:
 			// TODO.
 		}
 	}
 	return afterBodyIM, true
 }

 // Section 10.2.5.25.
 func afterAfterBodyIM(p *parser) (insertionMode, bool) {
 	switch p.tok.Type {
 	case ErrorToken:
 		// Stop parsing.
 		return nil, true
 	case TextToken:
 		// TODO.
 	case StartTagToken:
 		if p.tok.Data == "html" {
 			return useTheRulesFor(p, afterAfterBodyIM, inBodyIM)
 		}
 	}
 	return inBodyIM, false
 }

 // Parse returns the parse tree for the HTML from the given Reader.
 // The input is assumed to be UTF-8 encoded.
 func Parse(r io.Reader) (*Node, os.Error) {
 	p := &parser{
 		tokenizer: NewTokenizer(r),
 		doc: &Node{
 			Type: DocumentNode,
 		},
 		scripting:  true,
 		framesetOK: true,
 	}
 	// Iterate until EOF. Any other error will cause an early return.
 	im, consumed := initialIM, true
 	for {
 		if consumed {
 			if err := p.read(); err != nil {
 				if err == os.EOF {
 					break
 				}
 				return nil, err
 			}
 		}
 		im, consumed = im(p)
 	}
 	// Loop until the final token (the ErrorToken signifying EOF) is consumed.
 	for {
 		if im, consumed = im(p); consumed {
 			break
 		}
 	}
 	return p.doc, nil
 }
	// 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 (
	"io"
	"os"
	)

	// A NodeType is the type of a Node.
	type NodeType int

	const (
	ErrorNode NodeType = iota
	TextNode
	DocumentNode
	ElementNode
	CommentNode
	)

	// A Node consists of a NodeType and some Data (tag name for element nodes,
	// content for text) and are part of a tree of Nodes. Element nodes may also
	// contain a slice of Attributes. Data is unescaped, so that it looks like
	// "a<b" rather than "a<b".
	type Node struct {
	Parent *Node
	Child []*Node
	Type NodeType
	Data string
	Attr []Attribute
	}

	// A parser implements the HTML5 parsing algorithm:
	// http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.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 re-interpreted as a two-token sequence:
	// <hr> followed by </hr>. hasSelfClosingToken is true if we have just read
	// the synthetic start tag and the next one due is the matching end tag.
	hasSelfClosingToken bool
	// doc is the document root element.
	doc *Node
	// The stack of open elements (section 10.2.3.2).
	stack []*Node
	// Element pointers (section 10.2.3.4).
	head, form *Node
	// Other parsing state flags (section 10.2.3.5).
	scripting, framesetOK bool
	}

	// push pushes onto the stack of open elements.
	func (p parser) push(n Node) {
	p.stack = append(p.stack, n)
	}

	// top returns the top of the stack of open elements.
	// This is also known as the current node.
	func (p parser) top() Node {
	if n := len(p.stack); n > 0 {
	return p.stack[n-1]
	}
	return p.doc
	}

	// pop pops the top of the stack of open elements.
	// It will panic if the stack is empty.
	func (p parser) pop() Node {
	n := len(p.stack)
	ret := p.stack[n-1]
	p.stack = p.stack[:n-1]
	return ret
	}

	// stopTags for use in popUntil. These come from section 10.2.3.2.
	var (
	defaultScopeStopTags = []string{"applet", "caption", "html", "table", "td", "th", "marquee", "object"}
	listItemScopeStopTags = []string{"applet", "caption", "html", "table", "td", "th", "marquee", "object", "ol", "ul"}
	buttonScopeStopTags = []string{"applet", "caption", "html", "table", "td", "th", "marquee", "object", "button"}
	tableScopeStopTags = []string{"html", "table"}
	)

	// popUntil pops the stack of open elements at the highest element whose tag
	// is in matchTags, provided there is no higher element in stopTags. It returns
	// whether or not there was such an element. If there was not, popUntil leaves
	// the stack unchanged.
	//
	// For example, if the stack was:
	// ["html", "body", "font", "table", "b", "i", "u"]
	// then popUntil([]string{"html, "table"}, "font") would return false, but
	// popUntil([]string{"html, "table"}, "i") would return true and the resultant
	// stack would be:
	// ["html", "body", "font", "table", "b"]
	//
	// If an element's tag is in both stopTags 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 stopTags). For example,
	// popUntil([]string{"html, "table"}, "table") would return true and leave:
	// ["html", "body", "font"]
	func (p *parser) popUntil(stopTags []string, matchTags ...string) bool {
	for i := len(p.stack) - 1; i >= 0; i-- {
	tag := p.stack[i].Data
	for _, t := range matchTags {
	if t == tag {
	p.stack = p.stack[:i]
	return true
	}
	}
	for _, t := range stopTags {
	if t == tag {
	return false
	}
	}
	}
	return false
	}

	// addChild adds a child node n to the top element, and pushes n if it is an
	// element node (text nodes are not part of the stack of open elements).
	func (p parser) addChild(n Node) {
	m := p.top()
	m.Child = append(m.Child, n)
	if n.Type == ElementNode {
	p.push(n)
	}
	}

	// addText calls addChild with a text node.
	func (p *parser) addText(text string) {
	// TODO: merge s with previous text, if the preceding node is a text node.
	// TODO: distinguish whitespace text from others.
	p.addChild(&Node{
	Type: TextNode,
	Data: text,
	})
	}

	// addElement calls addChild with an element node.
	func (p *parser) addElement(tag string, attr []Attribute) {
	p.addChild(&Node{
	Type: ElementNode,
	Data: tag,
	Attr: attr,
	})
	}

	// Section 10.2.3.3.
	func (p *parser) addFormattingElement(tag string, attr []Attribute) {
	p.addElement(tag, attr)
	// TODO.
	}

	// Section 10.2.3.3.
	func (p *parser) reconstructActiveFormattingElements() {
	// TODO.
	}

	// read reads the next token. This is usually from the tokenizer, but it may
	// be the synthesized end tag implied by a self-closing tag.
	func (p *parser) read() os.Error {
	if p.hasSelfClosingToken {
	p.hasSelfClosingToken = false
	p.tok.Type = EndTagToken
	p.tok.Attr = nil
	return nil
	}
	p.tokenizer.Next()
	p.tok = p.tokenizer.Token()
	switch p.tok.Type {
	case ErrorToken:
	return p.tokenizer.Error()
	case SelfClosingTagToken:
	p.hasSelfClosingToken = true
	p.tok.Type = StartTagToken
	}
	return nil
	}

	// Section 10.2.4.
	func (p *parser) acknowledgeSelfClosingTag() {
	p.hasSelfClosingToken = false
	}

	// An insertion mode (section 10.2.3.1) is the state transition function from
	// a particular state in the HTML5 parser's state machine. It updates the
	// parser's fields depending on parser.token (where ErrorToken means EOF). In
	// addition to returning the next insertionMode state, it also returns whether
	// the token was consumed.
	type insertionMode func(*parser) (insertionMode, bool)

	// useTheRulesFor runs the delegate insertionMode over p, returning the actual
	// insertionMode unless the delegate caused a state transition.
	// Section 10.2.3.1, "using the rules for".
	func useTheRulesFor(p *parser, actual, delegate insertionMode) (insertionMode, bool) {
	im, consumed := delegate(p)
	if im != delegate {
	return im, consumed
	}
	return actual, consumed
	}

	// Section 10.2.5.4.
	func initialIM(p *parser) (insertionMode, bool) {
	// TODO: check p.tok for DOCTYPE.
	return beforeHTMLIM, false
	}

	// Section 10.2.5.5.
	func beforeHTMLIM(p *parser) (insertionMode, bool) {
	var (
	add bool
	attr []Attribute
	implied bool
	)
	switch p.tok.Type {
	case ErrorToken:
	implied = true
	case TextToken:
	// TODO: distinguish whitespace text from others.
	implied = true
	case StartTagToken:
	if p.tok.Data == "html" {
	add = true
	attr = p.tok.Attr
	} else {
	implied = true
	}
	case EndTagToken:
	switch p.tok.Data {
	case "head", "body", "html", "br":
	implied = true
	default:
	// Ignore the token.
	}
	}
	if add \|\| implied {
	p.addElement("html", attr)
	}
	return beforeHeadIM, !implied
	}

	// Section 10.2.5.6.
	func beforeHeadIM(p *parser) (insertionMode, bool) {
	var (
	add bool
	attr []Attribute
	implied bool
	)
	switch p.tok.Type {
	case ErrorToken:
	implied = true
	case TextToken:
	// TODO: distinguish whitespace text from others.
	implied = true
	case StartTagToken:
	switch p.tok.Data {
	case "head":
	add = true
	attr = p.tok.Attr
	case "html":
	return useTheRulesFor(p, beforeHeadIM, inBodyIM)
	default:
	implied = true
	}
	case EndTagToken:
	switch p.tok.Data {
	case "head", "body", "html", "br":
	implied = true
	default:
	// Ignore the token.
	}
	}
	if add \|\| implied {
	p.addElement("head", attr)
	}
	return inHeadIM, !implied
	}

	// Section 10.2.5.7.
	func inHeadIM(p *parser) (insertionMode, bool) {
	var (
	pop bool
	implied bool
	)
	switch p.tok.Type {
	case ErrorToken, TextToken:
	implied = true
	case StartTagToken:
	switch p.tok.Data {
	case "meta":
	// TODO.
	case "script":
	// TODO.
	default:
	implied = true
	}
	case EndTagToken:
	if p.tok.Data == "head" {
	pop = true
	}
	// TODO.
	}
	if pop \|\| implied {
	n := p.pop()
	if n.Data != "head" {
	panic("html: bad parser state")
	}
	return afterHeadIM, !implied
	}
	return inHeadIM, !implied
	}

	// Section 10.2.5.9.
	func afterHeadIM(p *parser) (insertionMode, bool) {
	var (
	add bool
	attr []Attribute
	framesetOK bool
	implied bool
	)
	switch p.tok.Type {
	case ErrorToken, TextToken:
	implied = true
	framesetOK = true
	case StartTagToken:
	switch p.tok.Data {
	case "html":
	// TODO.
	case "body":
	add = true
	attr = p.tok.Attr
	framesetOK = false
	case "frameset":
	// TODO.
	case "base", "basefont", "bgsound", "link", "meta", "noframes", "script", "style", "title":
	// TODO.
	case "head":
	// TODO.
	default:
	implied = true
	framesetOK = true
	}
	case EndTagToken:
	// TODO.
	}
	if add \|\| implied {
	p.addElement("body", attr)
	p.framesetOK = framesetOK
	}
	return inBodyIM, !implied
	}

	// Section 10.2.5.10.
	func inBodyIM(p *parser) (insertionMode, bool) {
	var endP bool
	switch p.tok.Type {
	case TextToken:
	p.addText(p.tok.Data)
	p.framesetOK = false
	case StartTagToken:
	switch p.tok.Data {
	case "address", "article", "aside", "blockquote", "center", "details", "dir", "div", "dl", "fieldset", "figcaption", "figure", "footer", "header", "hgroup", "menu", "nav", "ol", "p", "section", "summary", "ul":
	// TODO: Do the proper "does the stack of open elements has a p element in button scope" algorithm in section 10.2.3.2.
	n := p.top()
	if n.Type == ElementNode && n.Data == "p" {
	endP = true
	} else {
	p.addElement(p.tok.Data, p.tok.Attr)
	}
	case "h1", "h2", "h3", "h4", "h5", "h6":
	// TODO: auto-insert </p> if necessary.
	switch n := p.top(); n.Data {
	case "h1", "h2", "h3", "h4", "h5", "h6":
	p.pop()
	}
	p.addElement(p.tok.Data, p.tok.Attr)
	case "b", "big", "code", "em", "font", "i", "s", "small", "strike", "strong", "tt", "u":
	p.reconstructActiveFormattingElements()
	p.addFormattingElement(p.tok.Data, p.tok.Attr)
	case "area", "br", "embed", "img", "input", "keygen", "wbr":
	p.reconstructActiveFormattingElements()
	p.addElement(p.tok.Data, p.tok.Attr)
	p.pop()
	p.acknowledgeSelfClosingTag()
	p.framesetOK = false
	case "table":
	// TODO: auto-insert </p> if necessary, depending on quirks mode.
	p.addElement(p.tok.Data, p.tok.Attr)
	p.framesetOK = false
	return inTableIM, true
	case "hr":
	// TODO: auto-insert </p> if necessary.
	p.addElement(p.tok.Data, p.tok.Attr)
	p.pop()
	p.acknowledgeSelfClosingTag()
	p.framesetOK = false
	default:
	// TODO.
	}
	case EndTagToken:
	switch p.tok.Data {
	case "body":
	// TODO: autoclose the stack of open elements.
	return afterBodyIM, true
	case "a", "b", "big", "code", "em", "font", "i", "nobr", "s", "small", "strike", "strong", "tt", "u":
	// TODO: implement the "adoption agency" algorithm:
	// http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#adoptionAgency
	if p.tok.Data == p.top().Data {
	p.pop()
	}
	default:
	// TODO.
	}
	}
	if endP {
	// TODO: do the proper algorithm.
	n := p.pop()
	if n.Type != ElementNode \|\| n.Data != "p" {
	panic("unreachable")
	}
	}
	return inBodyIM, !endP
	}

	// Section 10.2.5.12.
	func inTableIM(p *parser) (insertionMode, bool) {
	var (
	add bool
	data string
	attr []Attribute
	consumed bool
	)
	switch p.tok.Type {
	case ErrorToken:
	// Stop parsing.
	return nil, true
	case TextToken:
	// TODO.
	case StartTagToken:
	switch p.tok.Data {
	case "tbody", "tfoot", "thead":
	add = true
	data = p.tok.Data
	attr = p.tok.Attr
	consumed = true
	case "td", "th", "tr":
	add = true
	data = "tbody"
	default:
	// TODO.
	}
	case EndTagToken:
	switch p.tok.Data {
	case "table":
	if p.popUntil(tableScopeStopTags, "table") {
	// TODO: "reset the insertion mode appropriately" as per 10.2.3.1.
	return inBodyIM, false
	}
	// Ignore the token.
	return inTableIM, true
	case "body", "caption", "col", "colgroup", "html", "tbody", "td", "tfoot", "th", "thead", "tr":
	// Ignore the token.
	return inTableIM, true
	}
	}
	if add {
	// TODO: clear the stack back to a table context.
	p.addElement(data, attr)
	return inTableBodyIM, consumed
	}
	// TODO: return useTheRulesFor(inTableIM, inBodyIM, p) unless etc. etc. foster parenting.
	return inTableIM, true
	}

	// Section 10.2.5.16.
	func inTableBodyIM(p *parser) (insertionMode, bool) {
	var (
	add bool
	data string
	attr []Attribute
	consumed bool
	)
	switch p.tok.Type {
	case ErrorToken:
	// TODO.
	case TextToken:
	// TODO.
	case StartTagToken:
	switch p.tok.Data {
	case "tr":
	add = true
	data = p.tok.Data
	attr = p.tok.Attr
	consumed = true
	case "td", "th":
	add = true
	data = "tr"
	consumed = false
	default:
	// TODO.
	}
	case EndTagToken:
	switch p.tok.Data {
	case "table":
	if p.popUntil(tableScopeStopTags, "tbody", "thead", "tfoot") {
	return inTableIM, false
	}
	// Ignore the token.
	return inTableBodyIM, true
	case "body", "caption", "col", "colgroup", "html", "td", "th", "tr":
	// Ignore the token.
	return inTableBodyIM, true
	}
	}
	if add {
	// TODO: clear the stack back to a table body context.
	p.addElement(data, attr)
	return inRowIM, consumed
	}
	return useTheRulesFor(p, inTableBodyIM, inTableIM)
	}

	// Section 10.2.5.17.
	func inRowIM(p *parser) (insertionMode, bool) {
	switch p.tok.Type {
	case ErrorToken:
	// TODO.
	case TextToken:
	// TODO.
	case StartTagToken:
	switch p.tok.Data {
	case "td", "th":
	// TODO: clear the stack back to a table row context.
	p.addElement(p.tok.Data, p.tok.Attr)
	// TODO: insert a marker at the end of the list of active formatting elements.
	return inCellIM, true
	default:
	// TODO.
	}
	case EndTagToken:
	switch p.tok.Data {
	case "tr":
	// TODO.
	case "table":
	if p.popUntil(tableScopeStopTags, "tr") {
	return inTableBodyIM, false
	}
	// Ignore the token.
	return inRowIM, true
	case "tbody", "tfoot", "thead":
	// TODO.
	case "body", "caption", "col", "colgroup", "html", "td", "th":
	// Ignore the token.
	return inRowIM, true
	default:
	// TODO.
	}
	}
	return useTheRulesFor(p, inRowIM, inTableIM)
	}

	// Section 10.2.5.18.
	func inCellIM(p *parser) (insertionMode, bool) {
	var (
	closeTheCellAndReprocess bool
	)
	switch p.tok.Type {
	case StartTagToken:
	switch p.tok.Data {
	case "caption", "col", "colgroup", "tbody", "td", "tfoot", "th", "thead", "tr":
	// TODO: check for "td" or "th" in table scope.
	closeTheCellAndReprocess = true
	}
	case EndTagToken:
	switch p.tok.Data {
	case "td", "th":
	// TODO.
	case "body", "caption", "col", "colgroup", "html":
	// TODO.
	case "table", "tbody", "tfoot", "thead", "tr":
	// TODO: check for matching element in table scope.
	closeTheCellAndReprocess = true
	}
	}
	if closeTheCellAndReprocess {
	if p.popUntil(tableScopeStopTags, "td") \|\| p.popUntil(tableScopeStopTags, "th") {
	// TODO: clear the list of active formatting elements up to the last marker.
	return inRowIM, false
	}
	}
	return useTheRulesFor(p, inCellIM, inBodyIM)
	}

	// Section 10.2.5.22.
	func afterBodyIM(p *parser) (insertionMode, bool) {
	switch p.tok.Type {
	case ErrorToken:
	// TODO.
	case TextToken:
	// TODO.
	case StartTagToken:
	// TODO.
	case EndTagToken:
	switch p.tok.Data {
	case "html":
	// TODO: autoclose the stack of open elements.
	return afterAfterBodyIM, true
	default:
	// TODO.
	}
	}
	return afterBodyIM, true
	}

	// Section 10.2.5.25.
	func afterAfterBodyIM(p *parser) (insertionMode, bool) {
	switch p.tok.Type {
	case ErrorToken:
	// Stop parsing.
	return nil, true
	case TextToken:
	// TODO.
	case StartTagToken:
	if p.tok.Data == "html" {
	return useTheRulesFor(p, afterAfterBodyIM, inBodyIM)
	}
	}
	return inBodyIM, false
	}

	// Parse returns the parse tree for the HTML from the given Reader.
	// The input is assumed to be UTF-8 encoded.
	func Parse(r io.Reader) (*Node, os.Error) {
	p := &parser{
	tokenizer: NewTokenizer(r),
	doc: &Node{
	Type: DocumentNode,
	},
	scripting: true,
	framesetOK: true,
	}
	// Iterate until EOF. Any other error will cause an early return.
	im, consumed := initialIM, true
	for {
	if consumed {
	if err := p.read(); err != nil {
	if err == os.EOF {
	break
	}
	return nil, err
	}
	}
	im, consumed = im(p)
	}
	// Loop until the final token (the ErrorToken signifying EOF) is consumed.
	for {
	if im, consumed = im(p); consumed {
	break
	}
	}
	return p.doc, nil
	}