html: parse misnested formatting tags according to the HTML5 spec.
This is the "adoption agency" algorithm.
The test case input is "<a><p>X<a>Y</a>Z</p></a>". The correct parse is:
| <html>
| <head>
| <body>
| <a>
| <p>
| <a>
| "X"
| <a>
| "Y"
| "Z"
R=gri
CC=golang-dev
https://golang.org/cl/4771042
diff --git a/src/pkg/html/Makefile b/src/pkg/html/Makefile
index 00e1c05..28dc1a3 100644
--- a/src/pkg/html/Makefile
+++ b/src/pkg/html/Makefile
@@ -6,9 +6,11 @@
TARG=html
GOFILES=\
+ const.go\
doc.go\
entity.go\
escape.go\
+ node.go\
parse.go\
token.go\
diff --git a/src/pkg/html/const.go b/src/pkg/html/const.go
new file mode 100644
index 0000000..9078d26
--- /dev/null
+++ b/src/pkg/html/const.go
@@ -0,0 +1,90 @@
+// 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 html
+
+// Section 11.2.3.2 of the HTML5 specification says "The following elements
+// have varying levels of special parsing rules".
+// http://www.whatwg.org/specs/web-apps/current-work/multipage/parsing.html#the-stack-of-open-elements
+var isSpecialElement = map[string]bool{
+ "address": true,
+ "applet": true,
+ "area": true,
+ "article": true,
+ "aside": true,
+ "base": true,
+ "basefont": true,
+ "bgsound": true,
+ "blockquote": true,
+ "body": true,
+ "br": true,
+ "button": true,
+ "caption": true,
+ "center": true,
+ "col": true,
+ "colgroup": true,
+ "command": true,
+ "dd": true,
+ "details": true,
+ "dir": true,
+ "div": true,
+ "dl": true,
+ "dt": true,
+ "embed": true,
+ "fieldset": true,
+ "figcaption": true,
+ "figure": true,
+ "footer": true,
+ "form": true,
+ "frame": true,
+ "frameset": true,
+ "h1": true,
+ "h2": true,
+ "h3": true,
+ "h4": true,
+ "h5": true,
+ "h6": true,
+ "head": true,
+ "header": true,
+ "hgroup": true,
+ "hr": true,
+ "html": true,
+ "iframe": true,
+ "img": true,
+ "input": true,
+ "isindex": true,
+ "li": true,
+ "link": true,
+ "listing": true,
+ "marquee": true,
+ "menu": true,
+ "meta": true,
+ "nav": true,
+ "noembed": true,
+ "noframes": true,
+ "noscript": true,
+ "object": true,
+ "ol": true,
+ "p": true,
+ "param": true,
+ "plaintext": true,
+ "pre": true,
+ "script": true,
+ "section": true,
+ "select": true,
+ "style": true,
+ "summary": true,
+ "table": true,
+ "tbody": true,
+ "td": true,
+ "textarea": true,
+ "tfoot": true,
+ "th": true,
+ "thead": true,
+ "title": true,
+ "tr": true,
+ "ul": true,
+ "wbr": true,
+ "xmp": true,
+}
diff --git a/src/pkg/html/node.go b/src/pkg/html/node.go
new file mode 100644
index 0000000..595afd5
--- /dev/null
+++ b/src/pkg/html/node.go
@@ -0,0 +1,146 @@
+// 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 html
+
+// A NodeType is the type of a Node.
+type NodeType int
+
+const (
+ ErrorNode NodeType = iota
+ TextNode
+ DocumentNode
+ ElementNode
+ CommentNode
+ scopeMarkerNode
+)
+
+// Section 11.2.3.3 says "scope markers are inserted when entering applet
+// elements, buttons, object elements, marquees, table cells, and table
+// captions, and are used to prevent formatting from 'leaking'".
+var scopeMarker = Node{Type: scopeMarkerNode}
+
+// 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
+}
+
+// Add adds a node as a child of n.
+// It will panic if the child's parent is not nil.
+func (n *Node) Add(child *Node) {
+ if child.Parent != nil {
+ panic("html: Node.Add called for a child Node that already has a parent")
+ }
+ child.Parent = n
+ n.Child = append(n.Child, child)
+}
+
+// Remove removes a node as a child of n.
+// It will panic if the child's parent is not n.
+func (n *Node) Remove(child *Node) {
+ if child.Parent == n {
+ child.Parent = nil
+ for i, m := range n.Child {
+ if m == child {
+ copy(n.Child[i:], n.Child[i+1:])
+ j := len(n.Child) - 1
+ n.Child[j] = nil
+ n.Child = n.Child[:j]
+ return
+ }
+ }
+ }
+ panic("html: Node.Remove called for a non-child Node")
+}
+
+// reparentChildren reparents all of src's child nodes to dst.
+func reparentChildren(dst, src *Node) {
+ for _, n := range src.Child {
+ if n.Parent != src {
+ panic("html: nodes have an inconsistent parent/child relationship")
+ }
+ n.Parent = dst
+ }
+ dst.Child = append(dst.Child, src.Child...)
+ src.Child = nil
+}
+
+// clone returns a new node with the same type, data and attributes.
+// The clone has no parent and no children.
+func (n *Node) clone() *Node {
+ m := &Node{
+ Type: n.Type,
+ Data: n.Data,
+ Attr: make([]Attribute, len(n.Attr)),
+ }
+ copy(m.Attr, n.Attr)
+ return m
+}
+
+// nodeStack is a stack of nodes.
+type nodeStack []*Node
+
+// pop pops the stack. It will panic if s is empty.
+func (s *nodeStack) pop() *Node {
+ i := len(*s)
+ n := (*s)[i-1]
+ *s = (*s)[:i-1]
+ return n
+}
+
+// top returns the most recently pushed node, or nil if s is empty.
+func (s *nodeStack) top() *Node {
+ if i := len(*s); i > 0 {
+ return (*s)[i-1]
+ }
+ return nil
+}
+
+// index returns the index of the top-most occurence of n in the stack, or -1
+// if n is not present.
+func (s *nodeStack) index(n *Node) int {
+ for i := len(*s) - 1; i >= 0; i-- {
+ if (*s)[i] == n {
+ return i
+ }
+ }
+ return -1
+}
+
+// insert inserts a node at the given index.
+func (s *nodeStack) insert(i int, n *Node) {
+ (*s) = append(*s, nil)
+ copy((*s)[i+1:], (*s)[i:])
+ (*s)[i] = n
+}
+
+// remove removes a node from the stack. It is a no-op if n is not present.
+func (s *nodeStack) remove(n *Node) {
+ i := s.index(n)
+ if i == -1 {
+ return
+ }
+ copy((*s)[i:], (*s)[i+1:])
+ j := len(*s) - 1
+ (*s)[j] = nil
+ *s = (*s)[:j]
+}
+
+// forTag returns the top-most element node with the given tag.
+func (s *nodeStack) forTag(tag string) *Node {
+ for i := len(*s) - 1; i >= 0; i-- {
+ n := (*s)[i]
+ if n.Type == ElementNode && n.Data == tag {
+ return n
+ }
+ }
+ return nil
+}
diff --git a/src/pkg/html/parse.go b/src/pkg/html/parse.go
index 5f5d9bf..980c470 100644
--- a/src/pkg/html/parse.go
+++ b/src/pkg/html/parse.go
@@ -9,29 +9,6 @@
"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 {
@@ -45,37 +22,22 @@
hasSelfClosingToken bool
// doc is the document root element.
doc *Node
- // The stack of open elements (section 11.2.3.2).
- stack []*Node
+ // 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 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 11.2.3.2.
var (
defaultScopeStopTags = []string{"applet", "caption", "html", "table", "td", "th", "marquee", "object"}
@@ -102,11 +64,11 @@
// 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
}
}
@@ -122,10 +84,9 @@
// 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)
+ p.top().Add(n)
if n.Type == ElementNode {
- p.push(n)
+ p.oe = append(p.oe, n)
}
}
@@ -151,12 +112,47 @@
// 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 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
@@ -305,7 +301,7 @@
// TODO.
}
if pop || implied {
- n := p.pop()
+ n := p.oe.pop()
if n.Data != "head" {
panic("html: bad parser state")
}
@@ -359,6 +355,7 @@
var endP bool
switch p.tok.Type {
case TextToken:
+ p.reconstructActiveFormattingElements()
p.addText(p.tok.Data)
p.framesetOK = false
case StartTagToken:
@@ -375,16 +372,24 @@
// 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,7 +400,7 @@
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:
@@ -408,21 +413,17 @@
// 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()
- }
+ p.inBodyEndTagFormatting(p.tok.Data)
default:
// TODO: any other end tag
if p.tok.Data == p.top().Data {
- p.pop()
+ p.oe.pop()
}
}
}
if endP {
// TODO: do the proper algorithm.
- n := p.pop()
+ n := p.oe.pop()
if n.Type != ElementNode || n.Data != "p" {
panic("unreachable")
}
@@ -430,6 +431,122 @@
return inBodyIM, !endP
}
+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 (
@@ -540,7 +657,7 @@
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.
@@ -592,7 +709,7 @@
}
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
}
}
diff --git a/src/pkg/html/parse_test.go b/src/pkg/html/parse_test.go
index 3fa35d5..f22fa27 100644
--- a/src/pkg/html/parse_test.go
+++ b/src/pkg/html/parse_test.go
@@ -85,6 +85,8 @@
fmt.Fprintf(w, "%q", EscapeString(n.Data))
case CommentNode:
return os.NewError("COMMENT")
+ case scopeMarkerNode:
+ return os.NewError("unexpected scopeMarkerNode")
default:
return os.NewError("unknown node type")
}
@@ -119,7 +121,7 @@
rc := make(chan io.Reader)
go readDat(filename, rc)
// TODO(nigeltao): Process all test cases, not just a subset.
- for i := 0; i < 22; i++ {
+ for i := 0; i < 23; i++ {
// Parse the #data section.
b, err := ioutil.ReadAll(<-rc)
if err != nil {
