libgo/go/html/parse.go

   1 // Copyright 2010 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package html
   6
   7 import (
   8         "io"
   9         "strings"
  10 )
  11
  12 // A parser implements the HTML5 parsing algorithm:
  13 // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#tree-construction
  14 type parser struct {
  15         // tokenizer provides the tokens for the parser.
  16         tokenizer *Tokenizer
  17         // tok is the most recently read token.
  18         tok Token
  19         // Self-closing tags like <hr/> are re-interpreted as a two-token sequence:
  20         // <hr> followed by </hr>. hasSelfClosingToken is true if we have just read
  21         // the synthetic start tag and the next one due is the matching end tag.
  22         hasSelfClosingToken bool
  23         // doc is the document root element.
  24         doc *Node
  25         // The stack of open elements (section 11.2.3.2) and active formatting
  26         // elements (section 11.2.3.3).
  27         oe, afe nodeStack
  28         // Element pointers (section 11.2.3.4).
  29         head, form *Node
  30         // Other parsing state flags (section 11.2.3.5).
  31         scripting, framesetOK bool
  32         // originalIM is the insertion mode to go back to after completing a text
  33         // or inTableText insertion mode.
  34         originalIM insertionMode
  35         // fosterParenting is whether new elements should be inserted according to
  36         // the foster parenting rules (section 11.2.5.3).
  37         fosterParenting bool
  38 }
  39
  40 func (p *parser) top() *Node {
  41         if n := p.oe.top(); n != nil {
  42                 return n
  43         }
  44         return p.doc
  45 }
  46
  47 // stopTags for use in popUntil. These come from section 11.2.3.2.
  48 var (
  49         defaultScopeStopTags  = []string{"applet", "caption", "html", "table", "td", "th", "marquee", "object"}
  50         listItemScopeStopTags = []string{"applet", "caption", "html", "table", "td", "th", "marquee", "object", "ol", "ul"}
  51         buttonScopeStopTags   = []string{"applet", "caption", "html", "table", "td", "th", "marquee", "object", "button"}
  52         tableScopeStopTags    = []string{"html", "table"}
  53 )
  54
  55 // stopTags for use in clearStackToContext.
  56 var (
  57         tableRowContextStopTags = []string{"tr", "html"}
  58 )
  59
  60 // popUntil pops the stack of open elements at the highest element whose tag
  61 // is in matchTags, provided there is no higher element in stopTags. It returns
  62 // whether or not there was such an element. If there was not, popUntil leaves
  63 // the stack unchanged.
  64 //
  65 // For example, if the stack was:
  66 // ["html", "body", "font", "table", "b", "i", "u"]
  67 // then popUntil([]string{"html, "table"}, "font") would return false, but
  68 // popUntil([]string{"html, "table"}, "i") would return true and the resultant
  69 // stack would be:
  70 // ["html", "body", "font", "table", "b"]
  71 //
  72 // If an element's tag is in both stopTags and matchTags, then the stack will
  73 // be popped and the function returns true (provided, of course, there was no
  74 // higher element in the stack that was also in stopTags). For example,
  75 // popUntil([]string{"html, "table"}, "table") would return true and leave:
  76 // ["html", "body", "font"]
  77 func (p *parser) popUntil(stopTags []string, matchTags ...string) bool {
  78         if i := p.indexOfElementInScope(stopTags, matchTags...); i != -1 {
  79                 p.oe = p.oe[:i]
  80                 return true
  81         }
  82         return false
  83 }
  84
  85 // indexOfElementInScope returns the index in p.oe of the highest element
  86 // whose tag is in matchTags that is in scope according to stopTags.
  87 // If no matching element is in scope, it returns -1.
  88 func (p *parser) indexOfElementInScope(stopTags []string, matchTags ...string) int {
  89         for i := len(p.oe) - 1; i >= 0; i-- {
  90                 tag := p.oe[i].Data
  91                 for _, t := range matchTags {
  92                         if t == tag {
  93                                 return i
  94                         }
  95                 }
  96                 for _, t := range stopTags {
  97                         if t == tag {
  98                                 return -1
  99                         }
 100                 }
 101         }
 102         return -1
 103 }
 104
 105 // elementInScope is like popUntil, except that it doesn't modify the stack of
 106 // open elements.
 107 func (p *parser) elementInScope(stopTags []string, matchTags ...string) bool {
 108         return p.indexOfElementInScope(stopTags, matchTags...) != -1
 109 }
 110
 111 // addChild adds a child node n to the top element, and pushes n onto the stack
 112 // of open elements if it is an element node.
 113 func (p *parser) addChild(n *Node) {
 114         if p.fosterParenting {
 115                 p.fosterParent(n)
 116         } else {
 117                 p.top().Add(n)
 118         }
 119
 120         if n.Type == ElementNode {
 121                 p.oe = append(p.oe, n)
 122         }
 123 }
 124
 125 // fosterParent adds a child node according to the foster parenting rules.
 126 // Section 11.2.5.3, "foster parenting".
 127 func (p *parser) fosterParent(n *Node) {
 128         p.fosterParenting = false
 129         var table, parent *Node
 130         var i int
 131         for i = len(p.oe) - 1; i >= 0; i-- {
 132                 if p.oe[i].Data == "table" {
 133                         table = p.oe[i]
 134                         break
 135                 }
 136         }
 137
 138         if table == nil {
 139                 // The foster parent is the html element.
 140                 parent = p.oe[0]
 141         } else {
 142                 parent = table.Parent
 143         }
 144         if parent == nil {
 145                 parent = p.oe[i-1]
 146         }
 147
 148         var child *Node
 149         for i, child = range parent.Child {
 150                 if child == table {
 151                         break
 152                 }
 153         }
 154
 155         if i > 0 && parent.Child[i-1].Type == TextNode && n.Type == TextNode {
 156                 parent.Child[i-1].Data += n.Data
 157                 return
 158         }
 159
 160         if i == len(parent.Child) {
 161                 parent.Add(n)
 162         } else {
 163                 // Insert n into parent.Child at index i.
 164                 parent.Child = append(parent.Child[:i+1], parent.Child[i:]...)
 165                 parent.Child[i] = n
 166                 n.Parent = parent
 167         }
 168 }
 169
 170 // addText adds text to the preceding node if it is a text node, or else it
 171 // calls addChild with a new text node.
 172 func (p *parser) addText(text string) {
 173         // TODO: distinguish whitespace text from others.
 174         t := p.top()
 175         if i := len(t.Child); i > 0 && t.Child[i-1].Type == TextNode {
 176                 t.Child[i-1].Data += text
 177                 return
 178         }
 179         p.addChild(&Node{
 180                 Type: TextNode,
 181                 Data: text,
 182         })
 183 }
 184
 185 // addElement calls addChild with an element node.
 186 func (p *parser) addElement(tag string, attr []Attribute) {
 187         p.addChild(&Node{
 188                 Type: ElementNode,
 189                 Data: tag,
 190                 Attr: attr,
 191         })
 192 }
 193
 194 // Section 11.2.3.3.
 195 func (p *parser) addFormattingElement(tag string, attr []Attribute) {
 196         p.addElement(tag, attr)
 197         p.afe = append(p.afe, p.top())
 198         // TODO.
 199 }
 200
 201 // Section 11.2.3.3.
 202 func (p *parser) clearActiveFormattingElements() {
 203         for {
 204                 n := p.afe.pop()
 205                 if len(p.afe) == 0 || n.Type == scopeMarkerNode {
 206                         return
 207                 }
 208         }
 209 }
 210
 211 // Section 11.2.3.3.
 212 func (p *parser) reconstructActiveFormattingElements() {
 213         n := p.afe.top()
 214         if n == nil {
 215                 return
 216         }
 217         if n.Type == scopeMarkerNode || p.oe.index(n) != -1 {
 218                 return
 219         }
 220         i := len(p.afe) - 1
 221         for n.Type != scopeMarkerNode && p.oe.index(n) == -1 {
 222                 if i == 0 {
 223                         i = -1
 224                         break
 225                 }
 226                 i--
 227                 n = p.afe[i]
 228         }
 229         for {
 230                 i++
 231                 clone := p.afe[i].clone()
 232                 p.addChild(clone)
 233                 p.afe[i] = clone
 234                 if i == len(p.afe)-1 {
 235                         break
 236                 }
 237         }
 238 }
 239
 240 // read reads the next token. This is usually from the tokenizer, but it may
 241 // be the synthesized end tag implied by a self-closing tag.
 242 func (p *parser) read() error {
 243         if p.hasSelfClosingToken {
 244                 p.hasSelfClosingToken = false
 245                 p.tok.Type = EndTagToken
 246                 p.tok.Attr = nil
 247                 return nil
 248         }
 249         p.tokenizer.Next()
 250         p.tok = p.tokenizer.Token()
 251         switch p.tok.Type {
 252         case ErrorToken:
 253                 return p.tokenizer.Err()
 254         case SelfClosingTagToken:
 255                 p.hasSelfClosingToken = true
 256                 p.tok.Type = StartTagToken
 257         }
 258         return nil
 259 }
 260
 261 // Section 11.2.4.
 262 func (p *parser) acknowledgeSelfClosingTag() {
 263         p.hasSelfClosingToken = false
 264 }
 265
 266 // An insertion mode (section 11.2.3.1) is the state transition function from
 267 // a particular state in the HTML5 parser's state machine. It updates the
 268 // parser's fields depending on parser.token (where ErrorToken means EOF). In
 269 // addition to returning the next insertionMode state, it also returns whether
 270 // the token was consumed.
 271 type insertionMode func(*parser) (insertionMode, bool)
 272
 273 // useTheRulesFor runs the delegate insertionMode over p, returning the actual
 274 // insertionMode unless the delegate caused a state transition.
 275 // Section 11.2.3.1, "using the rules for".
 276 func useTheRulesFor(p *parser, actual, delegate insertionMode) (insertionMode, bool) {
 277         im, consumed := delegate(p)
 278         if p.originalIM == delegate {
 279                 p.originalIM = actual
 280         }
 281         if im != delegate {
 282                 return im, consumed
 283         }
 284         return actual, consumed
 285 }
 286
 287 // setOriginalIM sets the insertion mode to return to after completing a text or
 288 // inTableText insertion mode.
 289 // Section 11.2.3.1, "using the rules for".
 290 func (p *parser) setOriginalIM(im insertionMode) {
 291         if p.originalIM != nil {
 292                 panic("html: bad parser state: originalIM was set twice")
 293         }
 294         p.originalIM = im
 295 }
 296
 297 // Section 11.2.3.1, "reset the insertion mode".
 298 func (p *parser) resetInsertionMode() insertionMode {
 299         for i := len(p.oe) - 1; i >= 0; i-- {
 300                 n := p.oe[i]
 301                 if i == 0 {
 302                         // TODO: set n to the context element, for HTML fragment parsing.
 303                 }
 304                 switch n.Data {
 305                 case "select":
 306                         return inSelectIM
 307                 case "td", "th":
 308                         return inCellIM
 309                 case "tr":
 310                         return inRowIM
 311                 case "tbody", "thead", "tfoot":
 312                         return inTableBodyIM
 313                 case "caption":
 314                         // TODO: return inCaptionIM
 315                 case "colgroup":
 316                         // TODO: return inColumnGroupIM
 317                 case "table":
 318                         return inTableIM
 319                 case "head":
 320                         return inBodyIM
 321                 case "body":
 322                         return inBodyIM
 323                 case "frameset":
 324                         // TODO: return inFramesetIM
 325                 case "html":
 326                         return beforeHeadIM
 327                 }
 328         }
 329         return inBodyIM
 330 }
 331
 332 // Section 11.2.5.4.1.
 333 func initialIM(p *parser) (insertionMode, bool) {
 334         switch p.tok.Type {
 335         case CommentToken:
 336                 p.doc.Add(&Node{
 337                         Type: CommentNode,
 338                         Data: p.tok.Data,
 339                 })
 340                 return initialIM, true
 341         case DoctypeToken:
 342                 p.doc.Add(&Node{
 343                         Type: DoctypeNode,
 344                         Data: p.tok.Data,
 345                 })
 346                 return beforeHTMLIM, true
 347         }
 348         // TODO: set "quirks mode"? It's defined in the DOM spec instead of HTML5 proper,
 349         // and so switching on "quirks mode" might belong in a different package.
 350         return beforeHTMLIM, false
 351 }
 352
 353 // Section 11.2.5.4.2.
 354 func beforeHTMLIM(p *parser) (insertionMode, bool) {
 355         var (
 356                 add     bool
 357                 attr    []Attribute
 358                 implied bool
 359         )
 360         switch p.tok.Type {
 361         case ErrorToken:
 362                 implied = true
 363         case TextToken:
 364                 // TODO: distinguish whitespace text from others.
 365                 implied = true
 366         case StartTagToken:
 367                 if p.tok.Data == "html" {
 368                         add = true
 369                         attr = p.tok.Attr
 370                 } else {
 371                         implied = true
 372                 }
 373         case EndTagToken:
 374                 switch p.tok.Data {
 375                 case "head", "body", "html", "br":
 376                         implied = true
 377                 default:
 378                         // Ignore the token.
 379                 }
 380         case CommentToken:
 381                 p.doc.Add(&Node{
 382                         Type: CommentNode,
 383                         Data: p.tok.Data,
 384                 })
 385                 return beforeHTMLIM, true
 386         }
 387         if add || implied {
 388                 p.addElement("html", attr)
 389         }
 390         return beforeHeadIM, !implied
 391 }
 392
 393 // Section 11.2.5.4.3.
 394 func beforeHeadIM(p *parser) (insertionMode, bool) {
 395         var (
 396                 add     bool
 397                 attr    []Attribute
 398                 implied bool
 399         )
 400         switch p.tok.Type {
 401         case ErrorToken:
 402                 implied = true
 403         case TextToken:
 404                 // TODO: distinguish whitespace text from others.
 405                 implied = true
 406         case StartTagToken:
 407                 switch p.tok.Data {
 408                 case "head":
 409                         add = true
 410                         attr = p.tok.Attr
 411                 case "html":
 412                         return useTheRulesFor(p, beforeHeadIM, inBodyIM)
 413                 default:
 414                         implied = true
 415                 }
 416         case EndTagToken:
 417                 switch p.tok.Data {
 418                 case "head", "body", "html", "br":
 419                         implied = true
 420                 default:
 421                         // Ignore the token.
 422                 }
 423         case CommentToken:
 424                 p.addChild(&Node{
 425                         Type: CommentNode,
 426                         Data: p.tok.Data,
 427                 })
 428                 return beforeHeadIM, true
 429         }
 430         if add || implied {
 431                 p.addElement("head", attr)
 432                 p.head = p.top()
 433         }
 434         return inHeadIM, !implied
 435 }
 436
 437 const whitespace = " \t\r\n\f"
 438
 439 // Section 11.2.5.4.4.
 440 func inHeadIM(p *parser) (insertionMode, bool) {
 441         var (
 442                 pop     bool
 443                 implied bool
 444         )
 445         switch p.tok.Type {
 446         case ErrorToken:
 447                 implied = true
 448         case TextToken:
 449                 s := strings.TrimLeft(p.tok.Data, whitespace)
 450                 if len(s) < len(p.tok.Data) {
 451                         // Add the initial whitespace to the current node.
 452                         p.addText(p.tok.Data[:len(p.tok.Data)-len(s)])
 453                         if s == "" {
 454                                 return inHeadIM, true
 455                         }
 456                         p.tok.Data = s
 457                 }
 458                 implied = true
 459         case StartTagToken:
 460                 switch p.tok.Data {
 461                 case "base", "basefont", "bgsound", "command", "link", "meta":
 462                         p.addElement(p.tok.Data, p.tok.Attr)
 463                         p.oe.pop()
 464                         p.acknowledgeSelfClosingTag()
 465                 case "script", "title", "noscript", "noframes", "style":
 466                         p.addElement(p.tok.Data, p.tok.Attr)
 467                         p.setOriginalIM(inHeadIM)
 468                         return textIM, true
 469                 default:
 470                         implied = true
 471                 }
 472         case EndTagToken:
 473                 if p.tok.Data == "head" {
 474                         pop = true
 475                 }
 476                 // TODO.
 477         case CommentToken:
 478                 p.addChild(&Node{
 479                         Type: CommentNode,
 480                         Data: p.tok.Data,
 481                 })
 482                 return inHeadIM, true
 483         }
 484         if pop || implied {
 485                 n := p.oe.pop()
 486                 if n.Data != "head" {
 487                         panic("html: bad parser state: <head> element not found, in the in-head insertion mode")
 488                 }
 489                 return afterHeadIM, !implied
 490         }
 491         return inHeadIM, true
 492 }
 493
 494 // Section 11.2.5.4.6.
 495 func afterHeadIM(p *parser) (insertionMode, bool) {
 496         var (
 497                 add        bool
 498                 attr       []Attribute
 499                 framesetOK bool
 500                 implied    bool
 501         )
 502         switch p.tok.Type {
 503         case ErrorToken, TextToken:
 504                 implied = true
 505                 framesetOK = true
 506         case StartTagToken:
 507                 switch p.tok.Data {
 508                 case "html":
 509                         // TODO.
 510                 case "body":
 511                         add = true
 512                         attr = p.tok.Attr
 513                         framesetOK = false
 514                 case "frameset":
 515                         // TODO.
 516                 case "base", "basefont", "bgsound", "link", "meta", "noframes", "script", "style", "title":
 517                         p.oe = append(p.oe, p.head)
 518                         defer p.oe.pop()
 519                         return useTheRulesFor(p, afterHeadIM, inHeadIM)
 520                 case "head":
 521                         // TODO.
 522                 default:
 523                         implied = true
 524                         framesetOK = true
 525                 }
 526         case EndTagToken:
 527                 // TODO.
 528         case CommentToken:
 529                 p.addChild(&Node{
 530                         Type: CommentNode,
 531                         Data: p.tok.Data,
 532                 })
 533                 return afterHeadIM, true
 534         }
 535         if add || implied {
 536                 p.addElement("body", attr)
 537                 p.framesetOK = framesetOK
 538         }
 539         return inBodyIM, !implied
 540 }
 541
 542 // copyAttributes copies attributes of src not found on dst to dst.
 543 func copyAttributes(dst *Node, src Token) {
 544         if len(src.Attr) == 0 {
 545                 return
 546         }
 547         attr := map[string]string{}
 548         for _, a := range dst.Attr {
 549                 attr[a.Key] = a.Val
 550         }
 551         for _, a := range src.Attr {
 552                 if _, ok := attr[a.Key]; !ok {
 553                         dst.Attr = append(dst.Attr, a)
 554                         attr[a.Key] = a.Val
 555                 }
 556         }
 557 }
 558
 559 // Section 11.2.5.4.7.
 560 func inBodyIM(p *parser) (insertionMode, bool) {
 561         switch p.tok.Type {
 562         case TextToken:
 563                 p.reconstructActiveFormattingElements()
 564                 p.addText(p.tok.Data)
 565                 p.framesetOK = false
 566         case StartTagToken:
 567                 switch p.tok.Data {
 568                 case "address", "article", "aside", "blockquote", "center", "details", "dir", "div", "dl", "fieldset", "figcaption", "figure", "footer", "header", "hgroup", "menu", "nav", "ol", "p", "section", "summary", "ul":
 569                         p.popUntil(buttonScopeStopTags, "p")
 570                         p.addElement(p.tok.Data, p.tok.Attr)
 571                 case "h1", "h2", "h3", "h4", "h5", "h6":
 572                         p.popUntil(buttonScopeStopTags, "p")
 573                         switch n := p.top(); n.Data {
 574                         case "h1", "h2", "h3", "h4", "h5", "h6":
 575                                 p.oe.pop()
 576                         }
 577                         p.addElement(p.tok.Data, p.tok.Attr)
 578                 case "a":
 579                         for i := len(p.afe) - 1; i >= 0 && p.afe[i].Type != scopeMarkerNode; i-- {
 580                                 if n := p.afe[i]; n.Type == ElementNode && n.Data == "a" {
 581                                         p.inBodyEndTagFormatting("a")
 582                                         p.oe.remove(n)
 583                                         p.afe.remove(n)
 584                                         break
 585                                 }
 586                         }
 587                         p.reconstructActiveFormattingElements()
 588                         p.addFormattingElement(p.tok.Data, p.tok.Attr)
 589                 case "b", "big", "code", "em", "font", "i", "s", "small", "strike", "strong", "tt", "u":
 590                         p.reconstructActiveFormattingElements()
 591                         p.addFormattingElement(p.tok.Data, p.tok.Attr)
 592                 case "applet", "marquee", "object":
 593                         p.reconstructActiveFormattingElements()
 594                         p.addElement(p.tok.Data, p.tok.Attr)
 595                         p.afe = append(p.afe, &scopeMarker)
 596                         p.framesetOK = false
 597                 case "area", "br", "embed", "img", "input", "keygen", "wbr":
 598                         p.reconstructActiveFormattingElements()
 599                         p.addElement(p.tok.Data, p.tok.Attr)
 600                         p.oe.pop()
 601                         p.acknowledgeSelfClosingTag()
 602                         p.framesetOK = false
 603                 case "table":
 604                         p.popUntil(buttonScopeStopTags, "p") // TODO: skip this step in quirks mode.
 605                         p.addElement(p.tok.Data, p.tok.Attr)
 606                         p.framesetOK = false
 607                         return inTableIM, true
 608                 case "hr":
 609                         p.popUntil(buttonScopeStopTags, "p")
 610                         p.addElement(p.tok.Data, p.tok.Attr)
 611                         p.oe.pop()
 612                         p.acknowledgeSelfClosingTag()
 613                         p.framesetOK = false
 614                 case "select":
 615                         p.reconstructActiveFormattingElements()
 616                         p.addElement(p.tok.Data, p.tok.Attr)
 617                         p.framesetOK = false
 618                         // TODO: detect <select> inside a table.
 619                         return inSelectIM, true
 620                 case "li":
 621                         p.framesetOK = false
 622                         for i := len(p.oe) - 1; i >= 0; i-- {
 623                                 node := p.oe[i]
 624                                 switch node.Data {
 625                                 case "li":
 626                                         p.popUntil(listItemScopeStopTags, "li")
 627                                 case "address", "div", "p":
 628                                         continue
 629                                 default:
 630                                         if !isSpecialElement[node.Data] {
 631                                                 continue
 632                                         }
 633                                 }
 634                                 break
 635                         }
 636                         p.popUntil(buttonScopeStopTags, "p")
 637                         p.addElement("li", p.tok.Attr)
 638                 case "optgroup", "option":
 639                         if p.top().Data == "option" {
 640                                 p.oe.pop()
 641                         }
 642                         p.reconstructActiveFormattingElements()
 643                         p.addElement(p.tok.Data, p.tok.Attr)
 644                 case "body":
 645                         if len(p.oe) >= 2 {
 646                                 body := p.oe[1]
 647                                 if body.Type == ElementNode && body.Data == "body" {
 648                                         p.framesetOK = false
 649                                         copyAttributes(body, p.tok)
 650                                 }
 651                         }
 652                 case "base", "basefont", "bgsound", "command", "link", "meta", "noframes", "script", "style", "title":
 653                         return useTheRulesFor(p, inBodyIM, inHeadIM)
 654                 case "image":
 655                         p.tok.Data = "img"
 656                         return inBodyIM, false
 657                 default:
 658                         // TODO.
 659                         p.addElement(p.tok.Data, p.tok.Attr)
 660                 }
 661         case EndTagToken:
 662                 switch p.tok.Data {
 663                 case "body":
 664                         // TODO: autoclose the stack of open elements.
 665                         return afterBodyIM, true
 666                 case "p":
 667                         if !p.elementInScope(buttonScopeStopTags, "p") {
 668                                 p.addElement("p", nil)
 669                         }
 670                         p.popUntil(buttonScopeStopTags, "p")
 671                 case "a", "b", "big", "code", "em", "font", "i", "nobr", "s", "small", "strike", "strong", "tt", "u":
 672                         p.inBodyEndTagFormatting(p.tok.Data)
 673                 case "address", "article", "aside", "blockquote", "button", "center", "details", "dir", "div", "dl", "fieldset", "figcaption", "figure", "footer", "header", "hgroup", "listing", "menu", "nav", "ol", "pre", "section", "summary", "ul":
 674                         p.popUntil(defaultScopeStopTags, p.tok.Data)
 675                 case "applet", "marquee", "object":
 676                         if p.popUntil(defaultScopeStopTags, p.tok.Data) {
 677                                 p.clearActiveFormattingElements()
 678                         }
 679                 default:
 680                         p.inBodyEndTagOther(p.tok.Data)
 681                 }
 682         case CommentToken:
 683                 p.addChild(&Node{
 684                         Type: CommentNode,
 685                         Data: p.tok.Data,
 686                 })
 687         }
 688
 689         return inBodyIM, true
 690 }
 691
 692 func (p *parser) inBodyEndTagFormatting(tag string) {
 693         // This is the "adoption agency" algorithm, described at
 694         // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#adoptionAgency
 695
 696         // TODO: this is a fairly literal line-by-line translation of that algorithm.
 697         // Once the code successfully parses the comprehensive test suite, we should
 698         // refactor this code to be more idiomatic.
 699
 700         // Steps 1-3. The outer loop.
 701         for i := 0; i < 8; i++ {
 702                 // Step 4. Find the formatting element.
 703                 var formattingElement *Node
 704                 for j := len(p.afe) - 1; j >= 0; j-- {
 705                         if p.afe[j].Type == scopeMarkerNode {
 706                                 break
 707                         }
 708                         if p.afe[j].Data == tag {
 709                                 formattingElement = p.afe[j]
 710                                 break
 711                         }
 712                 }
 713                 if formattingElement == nil {
 714                         p.inBodyEndTagOther(tag)
 715                         return
 716                 }
 717                 feIndex := p.oe.index(formattingElement)
 718                 if feIndex == -1 {
 719                         p.afe.remove(formattingElement)
 720                         return
 721                 }
 722                 if !p.elementInScope(defaultScopeStopTags, tag) {
 723                         // Ignore the tag.
 724                         return
 725                 }
 726
 727                 // Steps 5-6. Find the furthest block.
 728                 var furthestBlock *Node
 729                 for _, e := range p.oe[feIndex:] {
 730                         if isSpecialElement[e.Data] {
 731                                 furthestBlock = e
 732                                 break
 733                         }
 734                 }
 735                 if furthestBlock == nil {
 736                         e := p.oe.pop()
 737                         for e != formattingElement {
 738                                 e = p.oe.pop()
 739                         }
 740                         p.afe.remove(e)
 741                         return
 742                 }
 743
 744                 // Steps 7-8. Find the common ancestor and bookmark node.
 745                 commonAncestor := p.oe[feIndex-1]
 746                 bookmark := p.afe.index(formattingElement)
 747
 748                 // Step 9. The inner loop. Find the lastNode to reparent.
 749                 lastNode := furthestBlock
 750                 node := furthestBlock
 751                 x := p.oe.index(node)
 752                 // Steps 9.1-9.3.
 753                 for j := 0; j < 3; j++ {
 754                         // Step 9.4.
 755                         x--
 756                         node = p.oe[x]
 757                         // Step 9.5.
 758                         if p.afe.index(node) == -1 {
 759                                 p.oe.remove(node)
 760                                 continue
 761                         }
 762                         // Step 9.6.
 763                         if node == formattingElement {
 764                                 break
 765                         }
 766                         // Step 9.7.
 767                         clone := node.clone()
 768                         p.afe[p.afe.index(node)] = clone
 769                         p.oe[p.oe.index(node)] = clone
 770                         node = clone
 771                         // Step 9.8.
 772                         if lastNode == furthestBlock {
 773                                 bookmark = p.afe.index(node) + 1
 774                         }
 775                         // Step 9.9.
 776                         if lastNode.Parent != nil {
 777                                 lastNode.Parent.Remove(lastNode)
 778                         }
 779                         node.Add(lastNode)
 780                         // Step 9.10.
 781                         lastNode = node
 782                 }
 783
 784                 // Step 10. Reparent lastNode to the common ancestor,
 785                 // or for misnested table nodes, to the foster parent.
 786                 if lastNode.Parent != nil {
 787                         lastNode.Parent.Remove(lastNode)
 788                 }
 789                 switch commonAncestor.Data {
 790                 case "table", "tbody", "tfoot", "thead", "tr":
 791                         p.fosterParent(lastNode)
 792                 default:
 793                         commonAncestor.Add(lastNode)
 794                 }
 795
 796                 // Steps 11-13. Reparent nodes from the furthest block's children
 797                 // to a clone of the formatting element.
 798                 clone := formattingElement.clone()
 799                 reparentChildren(clone, furthestBlock)
 800                 furthestBlock.Add(clone)
 801
 802                 // Step 14. Fix up the list of active formatting elements.
 803                 if oldLoc := p.afe.index(formattingElement); oldLoc != -1 && oldLoc < bookmark {
 804                         // Move the bookmark with the rest of the list.
 805                         bookmark--
 806                 }
 807                 p.afe.remove(formattingElement)
 808                 p.afe.insert(bookmark, clone)
 809
 810                 // Step 15. Fix up the stack of open elements.
 811                 p.oe.remove(formattingElement)
 812                 p.oe.insert(p.oe.index(furthestBlock)+1, clone)
 813         }
 814 }
 815
 816 // inBodyEndTagOther performs the "any other end tag" algorithm for inBodyIM.
 817 func (p *parser) inBodyEndTagOther(tag string) {
 818         for i := len(p.oe) - 1; i >= 0; i-- {
 819                 if p.oe[i].Data == tag {
 820                         p.oe = p.oe[:i]
 821                         break
 822                 }
 823                 if isSpecialElement[p.oe[i].Data] {
 824                         break
 825                 }
 826         }
 827 }
 828
 829 // Section 11.2.5.4.8.
 830 func textIM(p *parser) (insertionMode, bool) {
 831         switch p.tok.Type {
 832         case ErrorToken:
 833                 p.oe.pop()
 834         case TextToken:
 835                 p.addText(p.tok.Data)
 836                 return textIM, true
 837         case EndTagToken:
 838                 p.oe.pop()
 839         }
 840         o := p.originalIM
 841         p.originalIM = nil
 842         return o, p.tok.Type == EndTagToken
 843 }
 844
 845 // Section 11.2.5.4.9.
 846 func inTableIM(p *parser) (insertionMode, bool) {
 847         switch p.tok.Type {
 848         case ErrorToken:
 849                 // Stop parsing.
 850                 return nil, true
 851         case TextToken:
 852                 // TODO.
 853         case StartTagToken:
 854                 switch p.tok.Data {
 855                 case "tbody", "tfoot", "thead":
 856                         p.clearStackToContext(tableScopeStopTags)
 857                         p.addElement(p.tok.Data, p.tok.Attr)
 858                         return inTableBodyIM, true
 859                 case "td", "th", "tr":
 860                         p.clearStackToContext(tableScopeStopTags)
 861                         p.addElement("tbody", nil)
 862                         return inTableBodyIM, false
 863                 case "table":
 864                         if p.popUntil(tableScopeStopTags, "table") {
 865                                 return p.resetInsertionMode(), false
 866                         }
 867                         // Ignore the token.
 868                         return inTableIM, true
 869                 default:
 870                         // TODO.
 871                 }
 872         case EndTagToken:
 873                 switch p.tok.Data {
 874                 case "table":
 875                         if p.popUntil(tableScopeStopTags, "table") {
 876                                 return p.resetInsertionMode(), true
 877                         }
 878                         // Ignore the token.
 879                         return inTableIM, true
 880                 case "body", "caption", "col", "colgroup", "html", "tbody", "td", "tfoot", "th", "thead", "tr":
 881                         // Ignore the token.
 882                         return inTableIM, true
 883                 }
 884         case CommentToken:
 885                 p.addChild(&Node{
 886                         Type: CommentNode,
 887                         Data: p.tok.Data,
 888                 })
 889                 return inTableIM, true
 890         }
 891
 892         switch p.top().Data {
 893         case "table", "tbody", "tfoot", "thead", "tr":
 894                 p.fosterParenting = true
 895                 defer func() { p.fosterParenting = false }()
 896         }
 897
 898         return useTheRulesFor(p, inTableIM, inBodyIM)
 899 }
 900
 901 // clearStackToContext pops elements off the stack of open elements
 902 // until an element listed in stopTags is found.
 903 func (p *parser) clearStackToContext(stopTags []string) {
 904         for i := len(p.oe) - 1; i >= 0; i-- {
 905                 for _, tag := range stopTags {
 906                         if p.oe[i].Data == tag {
 907                                 p.oe = p.oe[:i+1]
 908                                 return
 909                         }
 910                 }
 911         }
 912 }
 913
 914 // Section 11.2.5.4.13.
 915 func inTableBodyIM(p *parser) (insertionMode, bool) {
 916         var (
 917                 add      bool
 918                 data     string
 919                 attr     []Attribute
 920                 consumed bool
 921         )
 922         switch p.tok.Type {
 923         case ErrorToken:
 924                 // TODO.
 925         case TextToken:
 926                 // TODO.
 927         case StartTagToken:
 928                 switch p.tok.Data {
 929                 case "tr":
 930                         add = true
 931                         data = p.tok.Data
 932                         attr = p.tok.Attr
 933                         consumed = true
 934                 case "td", "th":
 935                         add = true
 936                         data = "tr"
 937                         consumed = false
 938                 default:
 939                         // TODO.
 940                 }
 941         case EndTagToken:
 942                 switch p.tok.Data {
 943                 case "table":
 944                         if p.popUntil(tableScopeStopTags, "tbody", "thead", "tfoot") {
 945                                 return inTableIM, false
 946                         }
 947                         // Ignore the token.
 948                         return inTableBodyIM, true
 949                 case "body", "caption", "col", "colgroup", "html", "td", "th", "tr":
 950                         // Ignore the token.
 951                         return inTableBodyIM, true
 952                 }
 953         case CommentToken:
 954                 p.addChild(&Node{
 955                         Type: CommentNode,
 956                         Data: p.tok.Data,
 957                 })
 958                 return inTableBodyIM, true
 959         }
 960         if add {
 961                 // TODO: clear the stack back to a table body context.
 962                 p.addElement(data, attr)
 963                 return inRowIM, consumed
 964         }
 965         return useTheRulesFor(p, inTableBodyIM, inTableIM)
 966 }
 967
 968 // Section 11.2.5.4.14.
 969 func inRowIM(p *parser) (insertionMode, bool) {
 970         switch p.tok.Type {
 971         case ErrorToken:
 972                 // TODO.
 973         case TextToken:
 974                 // TODO.
 975         case StartTagToken:
 976                 switch p.tok.Data {
 977                 case "td", "th":
 978                         p.clearStackToContext(tableRowContextStopTags)
 979                         p.addElement(p.tok.Data, p.tok.Attr)
 980                         p.afe = append(p.afe, &scopeMarker)
 981                         return inCellIM, true
 982                 case "caption", "col", "colgroup", "tbody", "tfoot", "thead", "tr":
 983                         if p.popUntil(tableScopeStopTags, "tr") {
 984                                 return inTableBodyIM, false
 985                         }
 986                         // Ignore the token.
 987                         return inRowIM, true
 988                 default:
 989                         // TODO.
 990                 }
 991         case EndTagToken:
 992                 switch p.tok.Data {
 993                 case "tr":
 994                         if p.popUntil(tableScopeStopTags, "tr") {
 995                                 return inTableBodyIM, true
 996                         }
 997                         // Ignore the token.
 998                         return inRowIM, true
 999                 case "table":
1000                         if p.popUntil(tableScopeStopTags, "tr") {
1001                                 return inTableBodyIM, false
1002                         }
1003                         // Ignore the token.
1004                         return inRowIM, true
1005                 case "tbody", "tfoot", "thead":
1006                         // TODO.
1007                 case "body", "caption", "col", "colgroup", "html", "td", "th":
1008                         // Ignore the token.
1009                         return inRowIM, true
1010                 default:
1011                         // TODO.
1012                 }
1013         case CommentToken:
1014                 p.addChild(&Node{
1015                         Type: CommentNode,
1016                         Data: p.tok.Data,
1017                 })
1018                 return inRowIM, true
1019         }
1020         return useTheRulesFor(p, inRowIM, inTableIM)
1021 }
1022
1023 // Section 11.2.5.4.15.
1024 func inCellIM(p *parser) (insertionMode, bool) {
1025         var (
1026                 closeTheCellAndReprocess bool
1027         )
1028         switch p.tok.Type {
1029         case StartTagToken:
1030                 switch p.tok.Data {
1031                 case "caption", "col", "colgroup", "tbody", "td", "tfoot", "th", "thead", "tr":
1032                         // TODO: check for "td" or "th" in table scope.
1033                         closeTheCellAndReprocess = true
1034                 }
1035         case EndTagToken:
1036                 switch p.tok.Data {
1037                 case "td", "th":
1038                         if !p.popUntil(tableScopeStopTags, p.tok.Data) {
1039                                 // Ignore the token.
1040                                 return inCellIM, true
1041                         }
1042                         p.clearActiveFormattingElements()
1043                         return inRowIM, true
1044                 case "body", "caption", "col", "colgroup", "html":
1045                         // TODO.
1046                 case "table", "tbody", "tfoot", "thead", "tr":
1047                         // TODO: check for matching element in table scope.
1048                         closeTheCellAndReprocess = true
1049                 }
1050         case CommentToken:
1051                 p.addChild(&Node{
1052                         Type: CommentNode,
1053                         Data: p.tok.Data,
1054                 })
1055                 return inCellIM, true
1056         }
1057         if closeTheCellAndReprocess {
1058                 if p.popUntil(tableScopeStopTags, "td") || p.popUntil(tableScopeStopTags, "th") {
1059                         p.clearActiveFormattingElements()
1060                         return inRowIM, false
1061                 }
1062         }
1063         return useTheRulesFor(p, inCellIM, inBodyIM)
1064 }
1065
1066 // Section 11.2.5.4.16.
1067 func inSelectIM(p *parser) (insertionMode, bool) {
1068         endSelect := false
1069         switch p.tok.Type {
1070         case ErrorToken:
1071                 // TODO.
1072         case TextToken:
1073                 p.addText(p.tok.Data)
1074         case StartTagToken:
1075                 switch p.tok.Data {
1076                 case "html":
1077                         // TODO.
1078                 case "option":
1079                         if p.top().Data == "option" {
1080                                 p.oe.pop()
1081                         }
1082                         p.addElement(p.tok.Data, p.tok.Attr)
1083                 case "optgroup":
1084                         // TODO.
1085                 case "select":
1086                         endSelect = true
1087                 case "input", "keygen", "textarea":
1088                         // TODO.
1089                 case "script":
1090                         // TODO.
1091                 default:
1092                         // Ignore the token.
1093                 }
1094         case EndTagToken:
1095                 switch p.tok.Data {
1096                 case "option":
1097                         // TODO.
1098                 case "optgroup":
1099                         // TODO.
1100                 case "select":
1101                         endSelect = true
1102                 default:
1103                         // Ignore the token.
1104                 }
1105         case CommentToken:
1106                 p.doc.Add(&Node{
1107                         Type: CommentNode,
1108                         Data: p.tok.Data,
1109                 })
1110         }
1111         if endSelect {
1112                 for i := len(p.oe) - 1; i >= 0; i-- {
1113                         switch p.oe[i].Data {
1114                         case "select":
1115                                 p.oe = p.oe[:i]
1116                                 return p.resetInsertionMode(), true
1117                         case "option", "optgroup":
1118                                 continue
1119                         default:
1120                                 // Ignore the token.
1121                                 return inSelectIM, true
1122                         }
1123                 }
1124         }
1125         return inSelectIM, true
1126 }
1127
1128 // Section 11.2.5.4.18.
1129 func afterBodyIM(p *parser) (insertionMode, bool) {
1130         switch p.tok.Type {
1131         case ErrorToken:
1132                 // TODO.
1133         case TextToken:
1134                 // TODO.
1135         case StartTagToken:
1136                 // TODO.
1137         case EndTagToken:
1138                 switch p.tok.Data {
1139                 case "html":
1140                         // TODO: autoclose the stack of open elements.
1141                         return afterAfterBodyIM, true
1142                 default:
1143                         // TODO.
1144                 }
1145         case CommentToken:
1146                 // The comment is attached to the <html> element.
1147                 if len(p.oe) < 1 || p.oe[0].Data != "html" {
1148                         panic("html: bad parser state: <html> element not found, in the after-body insertion mode")
1149                 }
1150                 p.oe[0].Add(&Node{
1151                         Type: CommentNode,
1152                         Data: p.tok.Data,
1153                 })
1154                 return afterBodyIM, true
1155         }
1156         // TODO: should this be "return inBodyIM, true"?
1157         return afterBodyIM, true
1158 }
1159
1160 // Section 11.2.5.4.21.
1161 func afterAfterBodyIM(p *parser) (insertionMode, bool) {
1162         switch p.tok.Type {
1163         case ErrorToken:
1164                 // Stop parsing.
1165                 return nil, true
1166         case TextToken:
1167                 // TODO.
1168         case StartTagToken:
1169                 if p.tok.Data == "html" {
1170                         return useTheRulesFor(p, afterAfterBodyIM, inBodyIM)
1171                 }
1172         case CommentToken:
1173                 p.doc.Add(&Node{
1174                         Type: CommentNode,
1175                         Data: p.tok.Data,
1176                 })
1177                 return afterAfterBodyIM, true
1178         }
1179         return inBodyIM, false
1180 }
1181
1182 // Parse returns the parse tree for the HTML from the given Reader.
1183 // The input is assumed to be UTF-8 encoded.
1184 func Parse(r io.Reader) (*Node, error) {
1185         p := &parser{
1186                 tokenizer: NewTokenizer(r),
1187                 doc: &Node{
1188                         Type: DocumentNode,
1189                 },
1190                 scripting:  true,
1191                 framesetOK: true,
1192         }
1193         // Iterate until EOF. Any other error will cause an early return.
1194         im, consumed := initialIM, true
1195         for {
1196                 if consumed {
1197                         if err := p.read(); err != nil {
1198                                 if err == io.EOF {
1199                                         break
1200                                 }
1201                                 return nil, err
1202                         }
1203                 }
1204                 im, consumed = im(p)
1205         }
1206         // Loop until the final token (the ErrorToken signifying EOF) is consumed.
1207         for {
1208                 if im, consumed = im(p); consumed {
1209                         break
1210                 }
1211         }
1212         return p.doc, nil
1213 }