Update Go library to r60.

From-SVN: r178910

1 files changed, 223 insertions, 89 deletions

diff --git a/libgo/go/html/parse.go b/libgo/go/html/parse.go
index 2ef90a8..519ebe5 100644
--- a/libgo/go/html/parse.go
+++ b/libgo/go/html/parse.go
@@ -9,29 +9,6 @@ import (
 	"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 {
@@ -45,38 +22,23 @@ type parser struct {
 	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).
+	// The stack of open elements (section 11.2.3.2) and active formatting
+	// elements (section 11.2.3.3).
+	oe, afe nodeStack
+	// Element pointers (section 11.2.3.4).
 	head, form *Node
-	// Other parsing state flags (section 10.2.3.5).
+	// Other parsing state flags (section 11.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]
+	if n := p.oe.top(); n != nil {
+		return n
 	}
 	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.
+// stopTags for use in popUntil. These come from section 11.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"}
@@ -102,11 +64,11 @@ var (
 // 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 i := len(p.oe) - 1; i >= 0; i-- {
+		tag := p.oe[i].Data
 		for _, t := range matchTags {
 			if t == tag {
-				p.stack = p.stack[:i]
+				p.oe = p.oe[:i]
 				return true
 			}
 		}
@@ -119,20 +81,24 @@ func (p *parser) popUntil(stopTags []string, matchTags ...string) bool {
 	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).
+// 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) {
-	m := p.top()
-	m.Child = append(m.Child, n)
+	p.top().Add(n)
 	if n.Type == ElementNode {
-		p.push(n)
+		p.oe = append(p.oe, n)
 	}
 }
 
-// addText calls addChild with a text node.
+// 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) {
-	// TODO: merge s with previous text, if the preceding node is a text node.
 	// TODO: distinguish whitespace text from others.
+	t := p.top()
+	if i := len(t.Child); i > 0 && t.Child[i-1].Type == TextNode {
+		t.Child[i-1].Data += text
+		return
+	}
 	p.addChild(&Node{
 		Type: TextNode,
 		Data: text,
@@ -148,15 +114,50 @@ func (p *parser) addElement(tag string, attr []Attribute) {
 	})
 }
 
-// Section 10.2.3.3.
+// Section 11.2.3.3.
 func (p *parser) addFormattingElement(tag string, attr []Attribute) {
 	p.addElement(tag, attr)
+	p.afe = append(p.afe, p.top())
 	// TODO.
 }
 
-// Section 10.2.3.3.
+// Section 11.2.3.3.
+func (p *parser) clearActiveFormattingElements() {
+	for {
+		n := p.afe.pop()
+		if len(p.afe) == 0 || n.Type == scopeMarkerNode {
+			return
+		}
+	}
+}
+
+// Section 11.2.3.3.
 func (p *parser) reconstructActiveFormattingElements() {
-	// TODO.
+	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++
+		n = p.afe[i]
+		p.addChild(n.clone())
+		p.afe[i] = n
+		if i == len(p.afe)-1 {
+			break
+		}
+	}
 }
 
 // read reads the next token. This is usually from the tokenizer, but it may
@@ -180,12 +181,12 @@ func (p *parser) read() os.Error {
 	return nil
 }
 
-// Section 10.2.4.
+// Section 11.2.4.
 func (p *parser) acknowledgeSelfClosingTag() {
 	p.hasSelfClosingToken = false
 }
 
-// An insertion mode (section 10.2.3.1) is the state transition function from
+// An insertion mode (section 11.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
@@ -194,7 +195,7 @@ 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".
+// Section 11.2.3.1, "using the rules for".
 func useTheRulesFor(p *parser, actual, delegate insertionMode) (insertionMode, bool) {
 	im, consumed := delegate(p)
 	if im != delegate {
@@ -203,13 +204,21 @@ func useTheRulesFor(p *parser, actual, delegate insertionMode) (insertionMode, b
 	return actual, consumed
 }
 
-// Section 10.2.5.4.
+// Section 11.2.5.4.1.
 func initialIM(p *parser) (insertionMode, bool) {
-	// TODO: check p.tok for DOCTYPE.
+	if p.tok.Type == DoctypeToken {
+		p.addChild(&Node{
+			Type: DoctypeNode,
+			Data: p.tok.Data,
+		})
+		return beforeHTMLIM, true
+	}
+	// TODO: set "quirks mode"? It's defined in the DOM spec instead of HTML5 proper,
+	// and so switching on "quirks mode" might belong in a different package.
 	return beforeHTMLIM, false
 }
 
-// Section 10.2.5.5.
+// Section 11.2.5.4.2.
 func beforeHTMLIM(p *parser) (insertionMode, bool) {
 	var (
 		add     bool
@@ -243,7 +252,7 @@ func beforeHTMLIM(p *parser) (insertionMode, bool) {
 	return beforeHeadIM, !implied
 }
 
-// Section 10.2.5.6.
+// Section 11.2.5.4.3.
 func beforeHeadIM(p *parser) (insertionMode, bool) {
 	var (
 		add     bool
@@ -280,7 +289,7 @@ func beforeHeadIM(p *parser) (insertionMode, bool) {
 	return inHeadIM, !implied
 }
 
-// Section 10.2.5.7.
+// Section 11.2.5.4.4.
 func inHeadIM(p *parser) (insertionMode, bool) {
 	var (
 		pop     bool
@@ -305,7 +314,7 @@ func inHeadIM(p *parser) (insertionMode, bool) {
 		// TODO.
 	}
 	if pop || implied {
-		n := p.pop()
+		n := p.oe.pop()
 		if n.Data != "head" {
 			panic("html: bad parser state")
 		}
@@ -314,7 +323,7 @@ func inHeadIM(p *parser) (insertionMode, bool) {
 	return inHeadIM, !implied
 }
 
-// Section 10.2.5.9.
+// Section 11.2.5.4.6.
 func afterHeadIM(p *parser) (insertionMode, bool) {
 	var (
 		add        bool
@@ -354,17 +363,18 @@ func afterHeadIM(p *parser) (insertionMode, bool) {
 	return inBodyIM, !implied
 }
 
-// Section 10.2.5.10.
+// Section 11.2.5.4.7.
 func inBodyIM(p *parser) (insertionMode, bool) {
 	var endP bool
 	switch p.tok.Type {
 	case TextToken:
+		p.reconstructActiveFormattingElements()
 		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.
+			// TODO: Do the proper "does the stack of open elements has a p element in button scope" algorithm in section 11.2.3.2.
 			n := p.top()
 			if n.Type == ElementNode && n.Data == "p" {
 				endP = true
@@ -375,16 +385,24 @@ func inBodyIM(p *parser) (insertionMode, bool) {
 			// TODO: auto-insert </p> if necessary.
 			switch n := p.top(); n.Data {
 			case "h1", "h2", "h3", "h4", "h5", "h6":
-				p.pop()
+				p.oe.pop()
 			}
 			p.addElement(p.tok.Data, p.tok.Attr)
+		case "a":
+			if n := p.afe.forTag("a"); n != nil {
+				p.inBodyEndTagFormatting("a")
+				p.oe.remove(n)
+				p.afe.remove(n)
+			}
+			p.reconstructActiveFormattingElements()
+			p.addFormattingElement(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.oe.pop()
 			p.acknowledgeSelfClosingTag()
 			p.framesetOK = false
 		case "table":
@@ -395,11 +413,12 @@ func inBodyIM(p *parser) (insertionMode, bool) {
 		case "hr":
 			// TODO: auto-insert </p> if necessary.
 			p.addElement(p.tok.Data, p.tok.Attr)
-			p.pop()
+			p.oe.pop()
 			p.acknowledgeSelfClosingTag()
 			p.framesetOK = false
 		default:
 			// TODO.
+			p.addElement(p.tok.Data, p.tok.Attr)
 		}
 	case EndTagToken:
 		switch p.tok.Data {
@@ -407,18 +426,17 @@ func inBodyIM(p *parser) (insertionMode, bool) {
 			// 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
+			p.inBodyEndTagFormatting(p.tok.Data)
+		default:
+			// TODO: any other end tag
 			if p.tok.Data == p.top().Data {
-				p.pop()
+				p.oe.pop()
 			}
-		default:
-			// TODO.
 		}
 	}
 	if endP {
 		// TODO: do the proper algorithm.
-		n := p.pop()
+		n := p.oe.pop()
 		if n.Type != ElementNode || n.Data != "p" {
 			panic("unreachable")
 		}
@@ -426,7 +444,123 @@ func inBodyIM(p *parser) (insertionMode, bool) {
 	return inBodyIM, !endP
 }
 
-// Section 10.2.5.12.
+func (p *parser) inBodyEndTagFormatting(tag string) {
+	// This is the "adoption agency" algorithm, described at
+	// http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#adoptionAgency
+
+	// TODO: this is a fairly literal line-by-line translation of that algorithm.
+	// Once the code successfully parses the comprehensive test suite, we should
+	// refactor this code to be more idiomatic.
+
+	// Steps 1-3. The outer loop.
+	for i := 0; i < 8; i++ {
+		// Step 4. Find the formatting element.
+		var formattingElement *Node
+		for j := len(p.afe) - 1; j >= 0; j-- {
+			if p.afe[j].Type == scopeMarkerNode {
+				break
+			}
+			if p.afe[j].Data == tag {
+				formattingElement = p.afe[j]
+				break
+			}
+		}
+		if formattingElement == nil {
+			return
+		}
+		feIndex := p.oe.index(formattingElement)
+		if feIndex == -1 {
+			p.afe.remove(formattingElement)
+			return
+		}
+
+		// Steps 5-6. Find the furthest block.
+		var furthestBlock *Node
+		for _, e := range p.oe[feIndex:] {
+			if isSpecialElement[e.Data] {
+				furthestBlock = e
+				break
+			}
+		}
+		if furthestBlock == nil {
+			e := p.oe.pop()
+			for e != formattingElement {
+				e = p.oe.pop()
+			}
+			p.afe.remove(e)
+			return
+		}
+
+		// Steps 7-8. Find the common ancestor and bookmark node.
+		commonAncestor := p.oe[feIndex-1]
+		bookmark := p.afe.index(formattingElement)
+
+		// Step 9. The inner loop. Find the lastNode to reparent.
+		lastNode := furthestBlock
+		node := furthestBlock
+		x := p.oe.index(node)
+		// Steps 9.1-9.3.
+		for j := 0; j < 3; j++ {
+			// Step 9.4.
+			x--
+			node = p.oe[x]
+			// Step 9.5.
+			if p.afe.index(node) == -1 {
+				p.oe.remove(node)
+				continue
+			}
+			// Step 9.6.
+			if node == formattingElement {
+				break
+			}
+			// Step 9.7.
+			clone := node.clone()
+			p.afe[p.afe.index(node)] = clone
+			p.oe[p.oe.index(node)] = clone
+			node = clone
+			// Step 9.8.
+			if lastNode == furthestBlock {
+				bookmark = p.afe.index(node) + 1
+			}
+			// Step 9.9.
+			if lastNode.Parent != nil {
+				lastNode.Parent.Remove(lastNode)
+			}
+			node.Add(lastNode)
+			// Step 9.10.
+			lastNode = node
+		}
+
+		// Step 10. Reparent lastNode to the common ancestor,
+		// or for misnested table nodes, to the foster parent.
+		if lastNode.Parent != nil {
+			lastNode.Parent.Remove(lastNode)
+		}
+		switch commonAncestor.Data {
+		case "table", "tbody", "tfoot", "thead", "tr":
+			// TODO: fix up misnested table nodes; find the foster parent.
+			fallthrough
+		default:
+			commonAncestor.Add(lastNode)
+		}
+
+		// Steps 11-13. Reparent nodes from the furthest block's children
+		// to a clone of the formatting element.
+		clone := formattingElement.clone()
+		reparentChildren(clone, furthestBlock)
+		furthestBlock.Add(clone)
+
+		// Step 14. Fix up the list of active formatting elements.
+		p.afe.remove(formattingElement)
+		p.afe.insert(bookmark, clone)
+
+		// Step 15. Fix up the stack of open elements.
+		p.oe.remove(formattingElement)
+		p.oe.insert(p.oe.index(furthestBlock)+1, clone)
+	}
+}
+
+// Section 11.2.5.4.9.
 func inTableIM(p *parser) (insertionMode, bool) {
 	var (
 		add      bool
@@ -457,7 +591,7 @@ func inTableIM(p *parser) (insertionMode, bool) {
 		switch p.tok.Data {
 		case "table":
 			if p.popUntil(tableScopeStopTags, "table") {
-				// TODO: "reset the insertion mode appropriately" as per 10.2.3.1.
+				// TODO: "reset the insertion mode appropriately" as per 11.2.3.1.
 				return inBodyIM, false
 			}
 			// Ignore the token.
@@ -476,7 +610,7 @@ func inTableIM(p *parser) (insertionMode, bool) {
 	return inTableIM, true
 }
 
-// Section 10.2.5.16.
+// Section 11.2.5.4.13.
 func inTableBodyIM(p *parser) (insertionMode, bool) {
 	var (
 		add      bool
@@ -524,7 +658,7 @@ func inTableBodyIM(p *parser) (insertionMode, bool) {
 	return useTheRulesFor(p, inTableBodyIM, inTableIM)
 }
 
-// Section 10.2.5.17.
+// Section 11.2.5.4.14.
 func inRowIM(p *parser) (insertionMode, bool) {
 	switch p.tok.Type {
 	case ErrorToken:
@@ -536,7 +670,7 @@ func inRowIM(p *parser) (insertionMode, bool) {
 		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.
+			p.afe = append(p.afe, &scopeMarker)
 			return inCellIM, true
 		default:
 			// TODO.
@@ -563,7 +697,7 @@ func inRowIM(p *parser) (insertionMode, bool) {
 	return useTheRulesFor(p, inRowIM, inTableIM)
 }
 
-// Section 10.2.5.18.
+// Section 11.2.5.4.15.
 func inCellIM(p *parser) (insertionMode, bool) {
 	var (
 		closeTheCellAndReprocess bool
@@ -588,14 +722,14 @@ func inCellIM(p *parser) (insertionMode, bool) {
 	}
 	if closeTheCellAndReprocess {
 		if p.popUntil(tableScopeStopTags, "td") || p.popUntil(tableScopeStopTags, "th") {
-			// TODO: clear the list of active formatting elements up to the last marker.
+			p.clearActiveFormattingElements()
 			return inRowIM, false
 		}
 	}
 	return useTheRulesFor(p, inCellIM, inBodyIM)
 }
 
-// Section 10.2.5.22.
+// Section 11.2.5.4.18.
 func afterBodyIM(p *parser) (insertionMode, bool) {
 	switch p.tok.Type {
 	case ErrorToken:
@@ -616,7 +750,7 @@ func afterBodyIM(p *parser) (insertionMode, bool) {
 	return afterBodyIM, true
 }
 
-// Section 10.2.5.25.
+// Section 11.2.5.4.21.
 func afterAfterBodyIM(p *parser) (insertionMode, bool) {
 	switch p.tok.Type {
 	case ErrorToken: