Source/WebCore/html/parser/HTMLTreeBuilder.cpp

   1 /*
   2  * Copyright (C) 2010 Google, Inc. All Rights Reserved.
   3  * Copyright (C) 2011 Apple Inc. All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY GOOGLE INC. ``AS IS'' AND ANY
  15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL GOOGLE INC. OR
  18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #include "config.h"
  28 #include "HTMLTreeBuilder.h"
  29
  30 #include "AtomicHTMLToken.h"
  31 #include "DocumentFragment.h"
  32 #include "HTMLDocument.h"
  33 #include "HTMLDocumentParser.h"
  34 #include "HTMLFormElement.h"
  35 #include "HTMLNames.h"
  36 #include "HTMLParserIdioms.h"
  37 #include "HTMLStackItem.h"
  38 #include "HTMLTemplateElement.h"
  39 #include "HTMLToken.h"
  40 #include "HTMLTokenizer.h"
  41 #include "LocalizedStrings.h"
  42 #include "MathMLNames.h"
  43 #include "NotImplemented.h"
  44 #include "SVGNames.h"
  45 #include "XLinkNames.h"
  46 #include "XMLNSNames.h"
  47 #include "XMLNames.h"
  48 #include <wtf/MainThread.h>
  49 #include <wtf/unicode/CharacterNames.h>
  50
  51 namespace WebCore {
  52
  53 using namespace HTMLNames;
  54
  55 namespace {
  56
  57 inline bool isHTMLSpaceOrReplacementCharacter(UChar character)
  58 {
  59     return isHTMLSpace(character) || character == replacementCharacter;
  60 }
  61
  62 }
  63
  64 static TextPosition uninitializedPositionValue1()
  65 {
  66     return TextPosition(OrdinalNumber::fromOneBasedInt(-1), OrdinalNumber::first());
  67 }
  68
  69 static inline bool isAllWhitespace(const String& string)
  70 {
  71     return string.isAllSpecialCharacters<isHTMLSpace>();
  72 }
  73
  74 static inline bool isAllWhitespaceOrReplacementCharacters(const String& string)
  75 {
  76     return string.isAllSpecialCharacters<isHTMLSpaceOrReplacementCharacter>();
  77 }
  78
  79 static bool isNumberedHeaderTag(const AtomicString& tagName)
  80 {
  81     return tagName == h1Tag
  82         || tagName == h2Tag
  83         || tagName == h3Tag
  84         || tagName == h4Tag
  85         || tagName == h5Tag
  86         || tagName == h6Tag;
  87 }
  88
  89 static bool isCaptionColOrColgroupTag(const AtomicString& tagName)
  90 {
  91     return tagName == captionTag
  92         || tagName == colTag
  93         || tagName == colgroupTag;
  94 }
  95
  96 static bool isTableCellContextTag(const AtomicString& tagName)
  97 {
  98     return tagName == thTag || tagName == tdTag;
  99 }
 100
 101 static bool isTableBodyContextTag(const AtomicString& tagName)
 102 {
 103     return tagName == tbodyTag
 104         || tagName == tfootTag
 105         || tagName == theadTag;
 106 }
 107
 108 static bool isNonAnchorNonNobrFormattingTag(const AtomicString& tagName)
 109 {
 110     return tagName == bTag
 111         || tagName == bigTag
 112         || tagName == codeTag
 113         || tagName == emTag
 114         || tagName == fontTag
 115         || tagName == iTag
 116         || tagName == sTag
 117         || tagName == smallTag
 118         || tagName == strikeTag
 119         || tagName == strongTag
 120         || tagName == ttTag
 121         || tagName == uTag;
 122 }
 123
 124 static bool isNonAnchorFormattingTag(const AtomicString& tagName)
 125 {
 126     return tagName == nobrTag
 127         || isNonAnchorNonNobrFormattingTag(tagName);
 128 }
 129
 130 // http://www.whatwg.org/specs/web-apps/current-work/multipage/parsing.html#formatting
 131 static bool isFormattingTag(const AtomicString& tagName)
 132 {
 133     return tagName == aTag || isNonAnchorFormattingTag(tagName);
 134 }
 135
 136 static HTMLFormElement* closestFormAncestor(Element* element)
 137 {
 138     ASSERT(isMainThread());
 139     while (element) {
 140         if (element->hasTagName(formTag))
 141             return static_cast<HTMLFormElement*>(element);
 142         ContainerNode* parent = element->parentNode();
 143         if (!parent || !parent->isElementNode())
 144             return 0;
 145         element = static_cast<Element*>(parent);
 146     }
 147     return 0;
 148 }
 149
 150 class HTMLTreeBuilder::ExternalCharacterTokenBuffer {
 151     WTF_MAKE_NONCOPYABLE(ExternalCharacterTokenBuffer);
 152 public:
 153     explicit ExternalCharacterTokenBuffer(AtomicHTMLToken* token)
 154         : m_current(token->characters())
 155         , m_end(m_current + token->charactersLength())
 156         , m_isAll8BitData(token->isAll8BitData())
 157     {
 158         ASSERT(!isEmpty());
 159     }
 160
 161     explicit ExternalCharacterTokenBuffer(const String& string)
 162         : m_current(string.characters())
 163         , m_end(m_current + string.length())
 164         , m_isAll8BitData(string.length() && string.is8Bit())
 165     {
 166         ASSERT(!isEmpty());
 167     }
 168
 169     ~ExternalCharacterTokenBuffer()
 170     {
 171         ASSERT(isEmpty());
 172     }
 173
 174     bool isEmpty() const { return m_current == m_end; }
 175
 176     bool isAll8BitData() const { return m_isAll8BitData; }
 177
 178     void skipAtMostOneLeadingNewline()
 179     {
 180         ASSERT(!isEmpty());
 181         if (*m_current == '\n')
 182             ++m_current;
 183     }
 184
 185     void skipLeadingWhitespace()
 186     {
 187         skipLeading<isHTMLSpace>();
 188     }
 189
 190     String takeLeadingWhitespace()
 191     {
 192         return takeLeading<isHTMLSpace>();
 193     }
 194
 195     void skipLeadingNonWhitespace()
 196     {
 197         skipLeading<isNotHTMLSpace>();
 198     }
 199
 200     String takeRemaining()
 201     {
 202         ASSERT(!isEmpty());
 203         const UChar* start = m_current;
 204         m_current = m_end;
 205         size_t length = m_current - start;
 206
 207         if (isAll8BitData())
 208             return String::make8BitFrom16BitSource(start, length);
 209
 210         return String(start, length);
 211     }
 212
 213     void giveRemainingTo(StringBuilder& recipient)
 214     {
 215         recipient.append(m_current, m_end - m_current);
 216         m_current = m_end;
 217     }
 218
 219     String takeRemainingWhitespace()
 220     {
 221         ASSERT(!isEmpty());
 222         Vector<UChar> whitespace;
 223         do {
 224             UChar cc = *m_current++;
 225             if (isHTMLSpace(cc))
 226                 whitespace.append(cc);
 227         } while (m_current < m_end);
 228         // Returning the null string when there aren't any whitespace
 229         // characters is slightly cleaner semantically because we don't want
 230         // to insert a text node (as opposed to inserting an empty text node).
 231         if (whitespace.isEmpty())
 232             return String();
 233         return String::adopt(whitespace);
 234     }
 235
 236 private:
 237     template<bool characterPredicate(UChar)>
 238     void skipLeading()
 239     {
 240         ASSERT(!isEmpty());
 241         while (characterPredicate(*m_current)) {
 242             if (++m_current == m_end)
 243                 return;
 244         }
 245     }
 246
 247     template<bool characterPredicate(UChar)>
 248     String takeLeading()
 249     {
 250         ASSERT(!isEmpty());
 251         const UChar* start = m_current;
 252         skipLeading<characterPredicate>();
 253         if (start == m_current)
 254             return String();
 255         if (isAll8BitData())
 256             return String::make8BitFrom16BitSource(start, m_current - start);
 257         return String(start, m_current - start);
 258     }
 259
 260     const UChar* m_current;
 261     const UChar* m_end;
 262     bool m_isAll8BitData;
 263 };
 264
 265
 266 HTMLTreeBuilder::HTMLTreeBuilder(HTMLDocumentParser* parser, HTMLDocument* document, bool, const HTMLParserOptions& options)
 267     : m_framesetOk(true)
 268 #ifndef NDEBUG
 269     , m_isAttached(true)
 270 #endif
 271     , m_tree(document, options.maximumDOMTreeDepth)
 272     , m_insertionMode(InitialMode)
 273     , m_originalInsertionMode(InitialMode)
 274     , m_shouldSkipLeadingNewline(false)
 275     , m_parser(parser)
 276     , m_scriptToProcessStartPosition(uninitializedPositionValue1())
 277     , m_options(options)
 278 {
 279 }
 280
 281 // FIXME: Member variables should be grouped into self-initializing structs to
 282 // minimize code duplication between these constructors.
 283 HTMLTreeBuilder::HTMLTreeBuilder(HTMLDocumentParser* parser, DocumentFragment* fragment, Element* contextElement, FragmentScriptingPermission scriptingPermission, const HTMLParserOptions& options)
 284     : m_framesetOk(true)
 285 #ifndef NDEBUG
 286     , m_isAttached(true)
 287 #endif
 288     , m_fragmentContext(fragment, contextElement, scriptingPermission)
 289     , m_tree(fragment, scriptingPermission, options.maximumDOMTreeDepth)
 290     , m_insertionMode(InitialMode)
 291     , m_originalInsertionMode(InitialMode)
 292     , m_shouldSkipLeadingNewline(false)
 293     , m_parser(parser)
 294     , m_scriptToProcessStartPosition(uninitializedPositionValue1())
 295     , m_options(options)
 296 {
 297     ASSERT(isMainThread());
 298     // FIXME: This assertion will become invalid if <http://webkit.org/b/60316> is fixed.
 299     ASSERT(contextElement);
 300     if (contextElement) {
 301         // Steps 4.2-4.6 of the HTML5 Fragment Case parsing algorithm:
 302         // http://www.whatwg.org/specs/web-apps/current-work/multipage/the-end.html#fragment-case
 303         // For efficiency, we skip step 4.2 ("Let root be a new html element with no attributes")
 304         // and instead use the DocumentFragment as a root node.
 305         m_tree.openElements()->pushRootNode(HTMLStackItem::create(fragment, HTMLStackItem::ItemForDocumentFragmentNode));
 306
 307 #if ENABLE(TEMPLATE_ELEMENT)
 308         if (contextElement->hasLocalName(templateTag))
 309             m_templateInsertionModes.append(TemplateContentsMode);
 310 #endif
 311
 312         resetInsertionModeAppropriately();
 313         m_tree.setForm(closestFormAncestor(contextElement));
 314     }
 315 }
 316
 317 HTMLTreeBuilder::~HTMLTreeBuilder()
 318 {
 319 }
 320
 321 void HTMLTreeBuilder::detach()
 322 {
 323 #ifndef NDEBUG
 324     // This call makes little sense in fragment mode, but for consistency
 325     // DocumentParser expects detach() to always be called before it's destroyed.
 326     m_isAttached = false;
 327 #endif
 328     // HTMLConstructionSite might be on the callstack when detach() is called
 329     // otherwise we'd just call m_tree.clear() here instead.
 330     m_tree.detach();
 331 }
 332
 333 HTMLTreeBuilder::FragmentParsingContext::FragmentParsingContext()
 334     : m_fragment(0)
 335     , m_contextElement(0)
 336     , m_scriptingPermission(AllowScriptingContent)
 337 {
 338 }
 339
 340 HTMLTreeBuilder::FragmentParsingContext::FragmentParsingContext(DocumentFragment* fragment, Element* contextElement, FragmentScriptingPermission scriptingPermission)
 341     : m_fragment(fragment)
 342     , m_contextElement(contextElement)
 343     , m_scriptingPermission(scriptingPermission)
 344 {
 345     ASSERT(!fragment->hasChildNodes());
 346 }
 347
 348 HTMLTreeBuilder::FragmentParsingContext::~FragmentParsingContext()
 349 {
 350 }
 351
 352 PassRefPtr<Element> HTMLTreeBuilder::takeScriptToProcess(TextPosition& scriptStartPosition)
 353 {
 354     ASSERT(m_scriptToProcess);
 355     // Unpause ourselves, callers may pause us again when processing the script.
 356     // The HTML5 spec is written as though scripts are executed inside the tree
 357     // builder.  We pause the parser to exit the tree builder, and then resume
 358     // before running scripts.
 359     scriptStartPosition = m_scriptToProcessStartPosition;
 360     m_scriptToProcessStartPosition = uninitializedPositionValue1();
 361     return m_scriptToProcess.release();
 362 }
 363
 364 void HTMLTreeBuilder::constructTree(AtomicHTMLToken* token)
 365 {
 366     if (shouldProcessTokenInForeignContent(token))
 367         processTokenInForeignContent(token);
 368     else
 369         processToken(token);
 370
 371     if (m_parser->tokenizer()) {
 372         bool inForeignContent = !m_tree.isEmpty()
 373             && !m_tree.currentStackItem()->isInHTMLNamespace()
 374             && !HTMLElementStack::isHTMLIntegrationPoint(m_tree.currentStackItem())
 375             && !HTMLElementStack::isMathMLTextIntegrationPoint(m_tree.currentStackItem());
 376
 377         m_parser->tokenizer()->setForceNullCharacterReplacement(m_insertionMode == TextMode || inForeignContent);
 378         m_parser->tokenizer()->setShouldAllowCDATA(inForeignContent);
 379     }
 380
 381     m_tree.executeQueuedTasks();
 382     // We might be detached now.
 383 }
 384
 385 void HTMLTreeBuilder::processToken(AtomicHTMLToken* token)
 386 {
 387     switch (token->type()) {
 388     case HTMLToken::Uninitialized:
 389         ASSERT_NOT_REACHED();
 390         break;
 391     case HTMLToken::DOCTYPE:
 392         m_shouldSkipLeadingNewline = false;
 393         processDoctypeToken(token);
 394         break;
 395     case HTMLToken::StartTag:
 396         m_shouldSkipLeadingNewline = false;
 397         processStartTag(token);
 398         break;
 399     case HTMLToken::EndTag:
 400         m_shouldSkipLeadingNewline = false;
 401         processEndTag(token);
 402         break;
 403     case HTMLToken::Comment:
 404         m_shouldSkipLeadingNewline = false;
 405         processComment(token);
 406         return;
 407     case HTMLToken::Character:
 408         processCharacter(token);
 409         break;
 410     case HTMLToken::EndOfFile:
 411         m_shouldSkipLeadingNewline = false;
 412         processEndOfFile(token);
 413         break;
 414     }
 415 }
 416
 417 void HTMLTreeBuilder::processDoctypeToken(AtomicHTMLToken* token)
 418 {
 419     ASSERT(token->type() == HTMLToken::DOCTYPE);
 420     if (m_insertionMode == InitialMode) {
 421         m_tree.insertDoctype(token);
 422         setInsertionMode(BeforeHTMLMode);
 423         return;
 424     }
 425     if (m_insertionMode == InTableTextMode) {
 426         defaultForInTableText();
 427         processDoctypeToken(token);
 428         return;
 429     }
 430     parseError(token);
 431 }
 432
 433 void HTMLTreeBuilder::processFakeStartTag(const QualifiedName& tagName, const Vector<Attribute>& attributes)
 434 {
 435     // FIXME: We'll need a fancier conversion than just "localName" for SVG/MathML tags.
 436     AtomicHTMLToken fakeToken(HTMLToken::StartTag, tagName.localName(), attributes);
 437     processStartTag(&fakeToken);
 438 }
 439
 440 void HTMLTreeBuilder::processFakeEndTag(const AtomicString& tagName)
 441 {
 442     AtomicHTMLToken fakeToken(HTMLToken::EndTag, tagName);
 443     processEndTag(&fakeToken);
 444 }
 445
 446 void HTMLTreeBuilder::processFakeEndTag(const QualifiedName& tagName)
 447 {
 448     // FIXME: We'll need a fancier conversion than just "localName" for SVG/MathML tags.
 449     processFakeEndTag(tagName.localName());
 450 }
 451
 452 void HTMLTreeBuilder::processFakeCharacters(const String& characters)
 453 {
 454     ASSERT(!characters.isEmpty());
 455     ExternalCharacterTokenBuffer buffer(characters);
 456     processCharacterBuffer(buffer);
 457 }
 458
 459 void HTMLTreeBuilder::processFakePEndTagIfPInButtonScope()
 460 {
 461     if (!m_tree.openElements()->inButtonScope(pTag.localName()))
 462         return;
 463     AtomicHTMLToken endP(HTMLToken::EndTag, pTag.localName());
 464     processEndTag(&endP);
 465 }
 466
 467 Vector<Attribute> HTMLTreeBuilder::attributesForIsindexInput(AtomicHTMLToken* token)
 468 {
 469     Vector<Attribute> attributes = token->attributes();
 470     for (int i = attributes.size() - 1; i >= 0; --i) {
 471         const QualifiedName& name = attributes.at(i).name();
 472         if (name.matches(nameAttr) || name.matches(actionAttr) || name.matches(promptAttr))
 473             attributes.remove(i);
 474     }
 475
 476     attributes.append(Attribute(nameAttr, isindexTag.localName()));
 477     return attributes;
 478 }
 479
 480 void HTMLTreeBuilder::processIsindexStartTagForInBody(AtomicHTMLToken* token)
 481 {
 482     ASSERT(token->type() == HTMLToken::StartTag);
 483     ASSERT(token->name() == isindexTag);
 484     parseError(token);
 485     if (m_tree.form())
 486         return;
 487     notImplemented(); // Acknowledge self-closing flag
 488     processFakeStartTag(formTag);
 489     Attribute* actionAttribute = token->getAttributeItem(actionAttr);
 490     if (actionAttribute)
 491         m_tree.form()->setAttribute(actionAttr, actionAttribute->value());
 492     processFakeStartTag(hrTag);
 493     processFakeStartTag(labelTag);
 494     Attribute* promptAttribute = token->getAttributeItem(promptAttr);
 495     if (promptAttribute)
 496         processFakeCharacters(promptAttribute->value());
 497     else
 498         processFakeCharacters(searchableIndexIntroduction());
 499     processFakeStartTag(inputTag, attributesForIsindexInput(token));
 500     notImplemented(); // This second set of characters may be needed by non-english locales.
 501     processFakeEndTag(labelTag);
 502     processFakeStartTag(hrTag);
 503     processFakeEndTag(formTag);
 504 }
 505
 506 namespace {
 507
 508 bool isLi(const HTMLStackItem* item)
 509 {
 510     return item->hasTagName(liTag);
 511 }
 512
 513 bool isDdOrDt(const HTMLStackItem* item)
 514 {
 515     return item->hasTagName(ddTag)
 516         || item->hasTagName(dtTag);
 517 }
 518
 519 }
 520
 521 template <bool shouldClose(const HTMLStackItem*)>
 522 void HTMLTreeBuilder::processCloseWhenNestedTag(AtomicHTMLToken* token)
 523 {
 524     m_framesetOk = false;
 525     HTMLElementStack::ElementRecord* nodeRecord = m_tree.openElements()->topRecord();
 526     while (1) {
 527         RefPtr<HTMLStackItem> item = nodeRecord->stackItem();
 528         if (shouldClose(item.get())) {
 529             ASSERT(item->isElementNode());
 530             processFakeEndTag(item->localName());
 531             break;
 532         }
 533         if (item->isSpecialNode() && !item->hasTagName(addressTag) && !item->hasTagName(divTag) && !item->hasTagName(pTag))
 534             break;
 535         nodeRecord = nodeRecord->next();
 536     }
 537     processFakePEndTagIfPInButtonScope();
 538     m_tree.insertHTMLElement(token);
 539 }
 540
 541 typedef HashMap<AtomicString, QualifiedName> PrefixedNameToQualifiedNameMap;
 542
 543 static void mapLoweredLocalNameToName(PrefixedNameToQualifiedNameMap* map, QualifiedName** names, size_t length)
 544 {
 545     for (size_t i = 0; i < length; ++i) {
 546         const QualifiedName& name = *names[i];
 547         const AtomicString& localName = name.localName();
 548         AtomicString loweredLocalName = localName.lower();
 549         if (loweredLocalName != localName)
 550             map->add(loweredLocalName, name);
 551     }
 552 }
 553
 554 static void adjustSVGTagNameCase(AtomicHTMLToken* token)
 555 {
 556     static PrefixedNameToQualifiedNameMap* caseMap = 0;
 557     if (!caseMap) {
 558         caseMap = new PrefixedNameToQualifiedNameMap;
 559         QualifiedName** svgTags = SVGNames::getSVGTags();
 560         mapLoweredLocalNameToName(caseMap, svgTags, SVGNames::SVGTagsCount);
 561     }
 562
 563     const QualifiedName& casedName = caseMap->get(token->name());
 564     if (casedName.localName().isNull())
 565         return;
 566     token->setName(casedName.localName());
 567 }
 568
 569 template<QualifiedName** getAttrs(), unsigned length>
 570 static void adjustAttributes(AtomicHTMLToken* token)
 571 {
 572     static PrefixedNameToQualifiedNameMap* caseMap = 0;
 573     if (!caseMap) {
 574         caseMap = new PrefixedNameToQualifiedNameMap;
 575         QualifiedName** attrs = getAttrs();
 576         mapLoweredLocalNameToName(caseMap, attrs, length);
 577     }
 578
 579     for (unsigned i = 0; i < token->attributes().size(); ++i) {
 580         Attribute& tokenAttribute = token->attributes().at(i);
 581         const QualifiedName& casedName = caseMap->get(tokenAttribute.localName());
 582         if (!casedName.localName().isNull())
 583             tokenAttribute.parserSetName(casedName);
 584     }
 585 }
 586
 587 static void adjustSVGAttributes(AtomicHTMLToken* token)
 588 {
 589     adjustAttributes<SVGNames::getSVGAttrs, SVGNames::SVGAttrsCount>(token);
 590 }
 591
 592 static void adjustMathMLAttributes(AtomicHTMLToken* token)
 593 {
 594     adjustAttributes<MathMLNames::getMathMLAttrs, MathMLNames::MathMLAttrsCount>(token);
 595 }
 596
 597 static void addNamesWithPrefix(PrefixedNameToQualifiedNameMap* map, const AtomicString& prefix, QualifiedName** names, size_t length)
 598 {
 599     for (size_t i = 0; i < length; ++i) {
 600         QualifiedName* name = names[i];
 601         const AtomicString& localName = name->localName();
 602         AtomicString prefixColonLocalName = prefix + ':' + localName;
 603         QualifiedName nameWithPrefix(prefix, localName, name->namespaceURI());
 604         map->add(prefixColonLocalName, nameWithPrefix);
 605     }
 606 }
 607
 608 static void adjustForeignAttributes(AtomicHTMLToken* token)
 609 {
 610     static PrefixedNameToQualifiedNameMap* map = 0;
 611     if (!map) {
 612         map = new PrefixedNameToQualifiedNameMap;
 613
 614         QualifiedName** attrs = XLinkNames::getXLinkAttrs();
 615         addNamesWithPrefix(map, xlinkAtom, attrs, XLinkNames::XLinkAttrsCount);
 616
 617         attrs = XMLNames::getXMLAttrs();
 618         addNamesWithPrefix(map, xmlAtom, attrs, XMLNames::XMLAttrsCount);
 619
 620         map->add(WTF::xmlnsAtom, XMLNSNames::xmlnsAttr);
 621         map->add("xmlns:xlink", QualifiedName(xmlnsAtom, xlinkAtom, XMLNSNames::xmlnsNamespaceURI));
 622     }
 623
 624     for (unsigned i = 0; i < token->attributes().size(); ++i) {
 625         Attribute& tokenAttribute = token->attributes().at(i);
 626         const QualifiedName& name = map->get(tokenAttribute.localName());
 627         if (!name.localName().isNull())
 628             tokenAttribute.parserSetName(name);
 629     }
 630 }
 631
 632 void HTMLTreeBuilder::processStartTagForInBody(AtomicHTMLToken* token)
 633 {
 634     ASSERT(token->type() == HTMLToken::StartTag);
 635     if (token->name() == htmlTag) {
 636         processHtmlStartTagForInBody(token);
 637         return;
 638     }
 639     if (token->name() == baseTag
 640         || token->name() == basefontTag
 641         || token->name() == bgsoundTag
 642         || token->name() == commandTag
 643         || token->name() == linkTag
 644         || token->name() == metaTag
 645         || token->name() == noframesTag
 646         || token->name() == scriptTag
 647         || token->name() == styleTag
 648         || token->name() == titleTag) {
 649         bool didProcess = processStartTagForInHead(token);
 650         ASSERT_UNUSED(didProcess, didProcess);
 651         return;
 652     }
 653     if (token->name() == bodyTag) {
 654         parseError(token);
 655         bool fragmentOrTemplateCase = !m_tree.openElements()->secondElementIsHTMLBodyElement() || m_tree.openElements()->hasOnlyOneElement();
 656 #if ENABLE(TEMPLATE_ELEMENT)
 657         fragmentOrTemplateCase = fragmentOrTemplateCase || m_tree.openElements()->hasTemplateInHTMLScope();
 658 #endif
 659         if (fragmentOrTemplateCase) {
 660             ASSERT(isParsingFragmentOrTemplateContents());
 661             return;
 662         }
 663         m_framesetOk = false;
 664         m_tree.insertHTMLBodyStartTagInBody(token);
 665         return;
 666     }
 667     if (token->name() == framesetTag) {
 668         parseError(token);
 669         if (!m_tree.openElements()->secondElementIsHTMLBodyElement() || m_tree.openElements()->hasOnlyOneElement()) {
 670             ASSERT(isParsingFragmentOrTemplateContents());
 671             return;
 672         }
 673         if (!m_framesetOk)
 674             return;
 675         m_tree.openElements()->bodyElement()->remove(ASSERT_NO_EXCEPTION);
 676         m_tree.openElements()->popUntil(m_tree.openElements()->bodyElement());
 677         m_tree.openElements()->popHTMLBodyElement();
 678         ASSERT(m_tree.openElements()->top() == m_tree.openElements()->htmlElement());
 679         m_tree.insertHTMLElement(token);
 680         setInsertionMode(InFramesetMode);
 681         return;
 682     }
 683     if (token->name() == addressTag
 684         || token->name() == articleTag
 685         || token->name() == asideTag
 686         || token->name() == blockquoteTag
 687         || token->name() == centerTag
 688         || token->name() == detailsTag
 689         || token->name() == dirTag
 690         || token->name() == divTag
 691         || token->name() == dlTag
 692         || token->name() == fieldsetTag
 693         || token->name() == figcaptionTag
 694         || token->name() == figureTag
 695         || token->name() == footerTag
 696         || token->name() == headerTag
 697         || token->name() == hgroupTag
 698         || token->name() == mainTag
 699         || token->name() == menuTag
 700         || token->name() == navTag
 701         || token->name() == olTag
 702         || token->name() == pTag
 703         || token->name() == sectionTag
 704         || token->name() == summaryTag
 705         || token->name() == ulTag) {
 706         processFakePEndTagIfPInButtonScope();
 707         m_tree.insertHTMLElement(token);
 708         return;
 709     }
 710     if (isNumberedHeaderTag(token->name())) {
 711         processFakePEndTagIfPInButtonScope();
 712         if (m_tree.currentStackItem()->isNumberedHeaderElement()) {
 713             parseError(token);
 714             m_tree.openElements()->pop();
 715         }
 716         m_tree.insertHTMLElement(token);
 717         return;
 718     }
 719     if (token->name() == preTag || token->name() == listingTag) {
 720         processFakePEndTagIfPInButtonScope();
 721         m_tree.insertHTMLElement(token);
 722         m_shouldSkipLeadingNewline = true;
 723         m_framesetOk = false;
 724         return;
 725     }
 726     if (token->name() == formTag) {
 727         if (m_tree.form()) {
 728             parseError(token);
 729             return;
 730         }
 731         processFakePEndTagIfPInButtonScope();
 732         m_tree.insertHTMLFormElement(token);
 733         return;
 734     }
 735     if (token->name() == liTag) {
 736         processCloseWhenNestedTag<isLi>(token);
 737         return;
 738     }
 739     if (token->name() == ddTag || token->name() == dtTag) {
 740         processCloseWhenNestedTag<isDdOrDt>(token);
 741         return;
 742     }
 743     if (token->name() == plaintextTag) {
 744         processFakePEndTagIfPInButtonScope();
 745         m_tree.insertHTMLElement(token);
 746         if (m_parser->tokenizer())
 747             m_parser->tokenizer()->setState(HTMLTokenizer::PLAINTEXTState);
 748         return;
 749     }
 750     if (token->name() == buttonTag) {
 751         if (m_tree.openElements()->inScope(buttonTag)) {
 752             parseError(token);
 753             processFakeEndTag(buttonTag);
 754             processStartTag(token); // FIXME: Could we just fall through here?
 755             return;
 756         }
 757         m_tree.reconstructTheActiveFormattingElements();
 758         m_tree.insertHTMLElement(token);
 759         m_framesetOk = false;
 760         return;
 761     }
 762     if (token->name() == aTag) {
 763         Element* activeATag = m_tree.activeFormattingElements()->closestElementInScopeWithName(aTag.localName());
 764         if (activeATag) {
 765             parseError(token);
 766             processFakeEndTag(aTag);
 767             m_tree.activeFormattingElements()->remove(activeATag);
 768             if (m_tree.openElements()->contains(activeATag))
 769                 m_tree.openElements()->remove(activeATag);
 770         }
 771         m_tree.reconstructTheActiveFormattingElements();
 772         m_tree.insertFormattingElement(token);
 773         return;
 774     }
 775     if (isNonAnchorNonNobrFormattingTag(token->name())) {
 776         m_tree.reconstructTheActiveFormattingElements();
 777         m_tree.insertFormattingElement(token);
 778         return;
 779     }
 780     if (token->name() == nobrTag) {
 781         m_tree.reconstructTheActiveFormattingElements();
 782         if (m_tree.openElements()->inScope(nobrTag)) {
 783             parseError(token);
 784             processFakeEndTag(nobrTag);
 785             m_tree.reconstructTheActiveFormattingElements();
 786         }
 787         m_tree.insertFormattingElement(token);
 788         return;
 789     }
 790     if (token->name() == appletTag
 791         || token->name() == embedTag
 792         || token->name() == objectTag) {
 793         if (isParsingFragment() && !pluginContentIsAllowed(m_fragmentContext.scriptingPermission()))
 794             return;
 795     }
 796     if (token->name() == appletTag
 797         || token->name() == marqueeTag
 798         || token->name() == objectTag) {
 799         m_tree.reconstructTheActiveFormattingElements();
 800         m_tree.insertHTMLElement(token);
 801         m_tree.activeFormattingElements()->appendMarker();
 802         m_framesetOk = false;
 803         return;
 804     }
 805     if (token->name() == tableTag) {
 806         if (!m_tree.inQuirksMode() && m_tree.openElements()->inButtonScope(pTag))
 807             processFakeEndTag(pTag);
 808         m_tree.insertHTMLElement(token);
 809         m_framesetOk = false;
 810         setInsertionMode(InTableMode);
 811         return;
 812     }
 813     if (token->name() == imageTag) {
 814         parseError(token);
 815         // Apparently we're not supposed to ask.
 816         token->setName(imgTag.localName());
 817         // Note the fall through to the imgTag handling below!
 818     }
 819     if (token->name() == areaTag
 820         || token->name() == brTag
 821         || token->name() == embedTag
 822         || token->name() == imgTag
 823         || token->name() == keygenTag
 824         || token->name() == wbrTag) {
 825         m_tree.reconstructTheActiveFormattingElements();
 826         m_tree.insertSelfClosingHTMLElement(token);
 827         m_framesetOk = false;
 828         return;
 829     }
 830     if (token->name() == inputTag) {
 831         Attribute* typeAttribute = token->getAttributeItem(typeAttr);
 832         m_tree.reconstructTheActiveFormattingElements();
 833         m_tree.insertSelfClosingHTMLElement(token);
 834         if (!typeAttribute || !equalIgnoringCase(typeAttribute->value(), "hidden"))
 835             m_framesetOk = false;
 836         return;
 837     }
 838     if (token->name() == paramTag
 839         || token->name() == sourceTag
 840         || token->name() == trackTag) {
 841         m_tree.insertSelfClosingHTMLElement(token);
 842         return;
 843     }
 844     if (token->name() == hrTag) {
 845         processFakePEndTagIfPInButtonScope();
 846         m_tree.insertSelfClosingHTMLElement(token);
 847         m_framesetOk = false;
 848         return;
 849     }
 850     if (token->name() == isindexTag) {
 851         processIsindexStartTagForInBody(token);
 852         return;
 853     }
 854     if (token->name() == textareaTag) {
 855         m_tree.insertHTMLElement(token);
 856         m_shouldSkipLeadingNewline = true;
 857         if (m_parser->tokenizer())
 858             m_parser->tokenizer()->setState(HTMLTokenizer::RCDATAState);
 859         m_originalInsertionMode = m_insertionMode;
 860         m_framesetOk = false;
 861         setInsertionMode(TextMode);
 862         return;
 863     }
 864     if (token->name() == xmpTag) {
 865         processFakePEndTagIfPInButtonScope();
 866         m_tree.reconstructTheActiveFormattingElements();
 867         m_framesetOk = false;
 868         processGenericRawTextStartTag(token);
 869         return;
 870     }
 871     if (token->name() == iframeTag) {
 872         m_framesetOk = false;
 873         processGenericRawTextStartTag(token);
 874         return;
 875     }
 876     if (token->name() == noembedTag && m_options.pluginsEnabled) {
 877         processGenericRawTextStartTag(token);
 878         return;
 879     }
 880     if (token->name() == noscriptTag && m_options.scriptEnabled) {
 881         processGenericRawTextStartTag(token);
 882         return;
 883     }
 884     if (token->name() == selectTag) {
 885         m_tree.reconstructTheActiveFormattingElements();
 886         m_tree.insertHTMLElement(token);
 887         m_framesetOk = false;
 888         if (m_insertionMode == InTableMode
 889              || m_insertionMode == InCaptionMode
 890              || m_insertionMode == InColumnGroupMode
 891              || m_insertionMode == InTableBodyMode
 892              || m_insertionMode == InRowMode
 893              || m_insertionMode == InCellMode)
 894             setInsertionMode(InSelectInTableMode);
 895         else
 896             setInsertionMode(InSelectMode);
 897         return;
 898     }
 899     if (token->name() == optgroupTag || token->name() == optionTag) {
 900         if (m_tree.currentStackItem()->hasTagName(optionTag)) {
 901             AtomicHTMLToken endOption(HTMLToken::EndTag, optionTag.localName());
 902             processEndTag(&endOption);
 903         }
 904         m_tree.reconstructTheActiveFormattingElements();
 905         m_tree.insertHTMLElement(token);
 906         return;
 907     }
 908     if (token->name() == rpTag || token->name() == rtTag) {
 909         if (m_tree.openElements()->inScope(rubyTag.localName())) {
 910             m_tree.generateImpliedEndTags();
 911             if (!m_tree.currentStackItem()->hasTagName(rubyTag))
 912                 parseError(token);
 913         }
 914         m_tree.insertHTMLElement(token);
 915         return;
 916     }
 917     if (token->name() == MathMLNames::mathTag.localName()) {
 918         m_tree.reconstructTheActiveFormattingElements();
 919         adjustMathMLAttributes(token);
 920         adjustForeignAttributes(token);
 921         m_tree.insertForeignElement(token, MathMLNames::mathmlNamespaceURI);
 922         return;
 923     }
 924     if (token->name() == SVGNames::svgTag.localName()) {
 925         m_tree.reconstructTheActiveFormattingElements();
 926         adjustSVGAttributes(token);
 927         adjustForeignAttributes(token);
 928         m_tree.insertForeignElement(token, SVGNames::svgNamespaceURI);
 929         return;
 930     }
 931     if (isCaptionColOrColgroupTag(token->name())
 932         || token->name() == frameTag
 933         || token->name() == headTag
 934         || isTableBodyContextTag(token->name())
 935         || isTableCellContextTag(token->name())
 936         || token->name() == trTag) {
 937         parseError(token);
 938         return;
 939     }
 940 #if ENABLE(TEMPLATE_ELEMENT)
 941     if (token->name() == templateTag) {
 942         processTemplateStartTag(token);
 943         return;
 944     }
 945 #endif
 946     m_tree.reconstructTheActiveFormattingElements();
 947     m_tree.insertHTMLElement(token);
 948 }
 949
 950 #if ENABLE(TEMPLATE_ELEMENT)
 951 void HTMLTreeBuilder::processTemplateStartTag(AtomicHTMLToken* token)
 952 {
 953     m_tree.activeFormattingElements()->appendMarker();
 954     m_tree.insertHTMLElement(token);
 955     m_templateInsertionModes.append(TemplateContentsMode);
 956     setInsertionMode(TemplateContentsMode);
 957 }
 958
 959 void HTMLTreeBuilder::processTemplateEndTag(AtomicHTMLToken* token)
 960 {
 961     if (!m_tree.openElements()->hasTemplateInHTMLScope()) {
 962         ASSERT(m_templateInsertionModes.isEmpty());
 963         parseError(token);
 964         return;
 965     }
 966     m_tree.generateImpliedEndTags();
 967     if (!m_tree.currentStackItem()->hasLocalName(token->name()))
 968         parseError(token);
 969     m_tree.openElements()->popUntilPopped(token->name());
 970     m_tree.activeFormattingElements()->clearToLastMarker();
 971     m_templateInsertionModes.removeLast();
 972     resetInsertionModeAppropriately();
 973 }
 974
 975 bool HTMLTreeBuilder::popAllTemplatesForEndOfFile()
 976 {
 977     if (m_templateInsertionModes.isEmpty())
 978         return false;
 979
 980     while (!m_templateInsertionModes.isEmpty()) {
 981         if (m_tree.currentIsRootNode())
 982             return false;
 983         if (m_tree.currentNode()->hasTagName(templateTag))
 984             m_templateInsertionModes.removeLast();
 985         m_tree.openElements()->pop();
 986     }
 987
 988     resetInsertionModeAppropriately();
 989     return true;
 990 }
 991 #endif
 992
 993 bool HTMLTreeBuilder::processColgroupEndTagForInColumnGroup()
 994 {
 995     bool ignoreFakeEndTag = m_tree.currentIsRootNode();
 996 #if ENABLE(TEMPLATE_ELEMENT)
 997     ignoreFakeEndTag = ignoreFakeEndTag || m_tree.currentNode()->hasTagName(templateTag);
 998 #endif
 999
1000     if (ignoreFakeEndTag) {
1001         ASSERT(isParsingFragmentOrTemplateContents());
1002         // FIXME: parse error
1003         return false;
1004     }
1005     m_tree.openElements()->pop();
1006     setInsertionMode(InTableMode);
1007     return true;
1008 }
1009
1010 // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#close-the-cell
1011 void HTMLTreeBuilder::closeTheCell()
1012 {
1013     ASSERT(insertionMode() == InCellMode);
1014     if (m_tree.openElements()->inTableScope(tdTag)) {
1015         ASSERT(!m_tree.openElements()->inTableScope(thTag));
1016         processFakeEndTag(tdTag);
1017         return;
1018     }
1019     ASSERT(m_tree.openElements()->inTableScope(thTag));
1020     processFakeEndTag(thTag);
1021     ASSERT(insertionMode() == InRowMode);
1022 }
1023
1024 void HTMLTreeBuilder::processStartTagForInTable(AtomicHTMLToken* token)
1025 {
1026     ASSERT(token->type() == HTMLToken::StartTag);
1027     if (token->name() == captionTag) {
1028         m_tree.openElements()->popUntilTableScopeMarker();
1029         m_tree.activeFormattingElements()->appendMarker();
1030         m_tree.insertHTMLElement(token);
1031         setInsertionMode(InCaptionMode);
1032         return;
1033     }
1034     if (token->name() == colgroupTag) {
1035         m_tree.openElements()->popUntilTableScopeMarker();
1036         m_tree.insertHTMLElement(token);
1037         setInsertionMode(InColumnGroupMode);
1038         return;
1039     }
1040     if (token->name() == colTag) {
1041         processFakeStartTag(colgroupTag);
1042         ASSERT(InColumnGroupMode);
1043         processStartTag(token);
1044         return;
1045     }
1046     if (isTableBodyContextTag(token->name())) {
1047         m_tree.openElements()->popUntilTableScopeMarker();
1048         m_tree.insertHTMLElement(token);
1049         setInsertionMode(InTableBodyMode);
1050         return;
1051     }
1052     if (isTableCellContextTag(token->name())
1053         || token->name() == trTag) {
1054         processFakeStartTag(tbodyTag);
1055         ASSERT(insertionMode() == InTableBodyMode);
1056         processStartTag(token);
1057         return;
1058     }
1059     if (token->name() == tableTag) {
1060         parseError(token);
1061         if (!processTableEndTagForInTable()) {
1062             ASSERT(isParsingFragmentOrTemplateContents());
1063             return;
1064         }
1065         processStartTag(token);
1066         return;
1067     }
1068     if (token->name() == styleTag || token->name() == scriptTag) {
1069         processStartTagForInHead(token);
1070         return;
1071     }
1072     if (token->name() == inputTag) {
1073         Attribute* typeAttribute = token->getAttributeItem(typeAttr);
1074         if (typeAttribute && equalIgnoringCase(typeAttribute->value(), "hidden")) {
1075             parseError(token);
1076             m_tree.insertSelfClosingHTMLElement(token);
1077             return;
1078         }
1079         // Fall through to "anything else" case.
1080     }
1081     if (token->name() == formTag) {
1082         parseError(token);
1083         if (m_tree.form())
1084             return;
1085         m_tree.insertHTMLFormElement(token, true);
1086         m_tree.openElements()->pop();
1087         return;
1088     }
1089 #if ENABLE(TEMPLATE_ELEMENT)
1090     if (token->name() == templateTag) {
1091         processTemplateStartTag(token);
1092         return;
1093     }
1094 #endif
1095     parseError(token);
1096     HTMLConstructionSite::RedirectToFosterParentGuard redirecter(m_tree);
1097     processStartTagForInBody(token);
1098 }
1099
1100 void HTMLTreeBuilder::processStartTag(AtomicHTMLToken* token)
1101 {
1102     ASSERT(token->type() == HTMLToken::StartTag);
1103     switch (insertionMode()) {
1104     case InitialMode:
1105         ASSERT(insertionMode() == InitialMode);
1106         defaultForInitial();
1107         // Fall through.
1108     case BeforeHTMLMode:
1109         ASSERT(insertionMode() == BeforeHTMLMode);
1110         if (token->name() == htmlTag) {
1111             m_tree.insertHTMLHtmlStartTagBeforeHTML(token);
1112             setInsertionMode(BeforeHeadMode);
1113             return;
1114         }
1115         defaultForBeforeHTML();
1116         // Fall through.
1117     case BeforeHeadMode:
1118         ASSERT(insertionMode() == BeforeHeadMode);
1119         if (token->name() == htmlTag) {
1120             processHtmlStartTagForInBody(token);
1121             return;
1122         }
1123         if (token->name() == headTag) {
1124             m_tree.insertHTMLHeadElement(token);
1125             setInsertionMode(InHeadMode);
1126             return;
1127         }
1128         defaultForBeforeHead();
1129         // Fall through.
1130     case InHeadMode:
1131         ASSERT(insertionMode() == InHeadMode);
1132         if (processStartTagForInHead(token))
1133             return;
1134         defaultForInHead();
1135         // Fall through.
1136     case AfterHeadMode:
1137         ASSERT(insertionMode() == AfterHeadMode);
1138         if (token->name() == htmlTag) {
1139             processHtmlStartTagForInBody(token);
1140             return;
1141         }
1142         if (token->name() == bodyTag) {
1143             m_framesetOk = false;
1144             m_tree.insertHTMLBodyElement(token);
1145             setInsertionMode(InBodyMode);
1146             return;
1147         }
1148         if (token->name() == framesetTag) {
1149             m_tree.insertHTMLElement(token);
1150             setInsertionMode(InFramesetMode);
1151             return;
1152         }
1153         if (token->name() == baseTag
1154             || token->name() == basefontTag
1155             || token->name() == bgsoundTag
1156             || token->name() == linkTag
1157             || token->name() == metaTag
1158             || token->name() == noframesTag
1159             || token->name() == scriptTag
1160             || token->name() == styleTag
1161             || token->name() == titleTag) {
1162             parseError(token);
1163             ASSERT(m_tree.head());
1164             m_tree.openElements()->pushHTMLHeadElement(m_tree.headStackItem());
1165             processStartTagForInHead(token);
1166             m_tree.openElements()->removeHTMLHeadElement(m_tree.head());
1167             return;
1168         }
1169         if (token->name() == headTag) {
1170             parseError(token);
1171             return;
1172         }
1173         defaultForAfterHead();
1174         // Fall through
1175     case InBodyMode:
1176         ASSERT(insertionMode() == InBodyMode);
1177         processStartTagForInBody(token);
1178         break;
1179     case InTableMode:
1180         ASSERT(insertionMode() == InTableMode);
1181         processStartTagForInTable(token);
1182         break;
1183     case InCaptionMode:
1184         ASSERT(insertionMode() == InCaptionMode);
1185         if (isCaptionColOrColgroupTag(token->name())
1186             || isTableBodyContextTag(token->name())
1187             || isTableCellContextTag(token->name())
1188             || token->name() == trTag) {
1189             parseError(token);
1190             if (!processCaptionEndTagForInCaption()) {
1191                 ASSERT(isParsingFragment());
1192                 return;
1193             }
1194             processStartTag(token);
1195             return;
1196         }
1197         processStartTagForInBody(token);
1198         break;
1199     case InColumnGroupMode:
1200         ASSERT(insertionMode() == InColumnGroupMode);
1201         if (token->name() == htmlTag) {
1202             processHtmlStartTagForInBody(token);
1203             return;
1204         }
1205         if (token->name() == colTag) {
1206             m_tree.insertSelfClosingHTMLElement(token);
1207             return;
1208         }
1209 #if ENABLE(TEMPLATE_ELEMENT)
1210         if (token->name() == templateTag) {
1211             processTemplateStartTag(token);
1212             return;
1213         }
1214 #endif
1215         if (!processColgroupEndTagForInColumnGroup()) {
1216             ASSERT(isParsingFragmentOrTemplateContents());
1217             return;
1218         }
1219         processStartTag(token);
1220         break;
1221     case InTableBodyMode:
1222         ASSERT(insertionMode() == InTableBodyMode);
1223         if (token->name() == trTag) {
1224             m_tree.openElements()->popUntilTableBodyScopeMarker(); // How is there ever anything to pop?
1225             m_tree.insertHTMLElement(token);
1226             setInsertionMode(InRowMode);
1227             return;
1228         }
1229         if (isTableCellContextTag(token->name())) {
1230             parseError(token);
1231             processFakeStartTag(trTag);
1232             ASSERT(insertionMode() == InRowMode);
1233             processStartTag(token);
1234             return;
1235         }
1236         if (isCaptionColOrColgroupTag(token->name()) || isTableBodyContextTag(token->name())) {
1237             // FIXME: This is slow.
1238             if (!m_tree.openElements()->inTableScope(tbodyTag) && !m_tree.openElements()->inTableScope(theadTag) && !m_tree.openElements()->inTableScope(tfootTag)) {
1239                 ASSERT(isParsingFragmentOrTemplateContents());
1240                 parseError(token);
1241                 return;
1242             }
1243             m_tree.openElements()->popUntilTableBodyScopeMarker();
1244             ASSERT(isTableBodyContextTag(m_tree.currentStackItem()->localName()));
1245             processFakeEndTag(m_tree.currentStackItem()->localName());
1246             processStartTag(token);
1247             return;
1248         }
1249         processStartTagForInTable(token);
1250         break;
1251     case InRowMode:
1252         ASSERT(insertionMode() == InRowMode);
1253         if (isTableCellContextTag(token->name())) {
1254             m_tree.openElements()->popUntilTableRowScopeMarker();
1255             m_tree.insertHTMLElement(token);
1256             setInsertionMode(InCellMode);
1257             m_tree.activeFormattingElements()->appendMarker();
1258             return;
1259         }
1260         if (token->name() == trTag
1261             || isCaptionColOrColgroupTag(token->name())
1262             || isTableBodyContextTag(token->name())) {
1263             if (!processTrEndTagForInRow()) {
1264                 ASSERT(isParsingFragmentOrTemplateContents());
1265                 return;
1266             }
1267             ASSERT(insertionMode() == InTableBodyMode);
1268             processStartTag(token);
1269             return;
1270         }
1271         processStartTagForInTable(token);
1272         break;
1273     case InCellMode:
1274         ASSERT(insertionMode() == InCellMode);
1275         if (isCaptionColOrColgroupTag(token->name())
1276             || isTableCellContextTag(token->name())
1277             || token->name() == trTag
1278             || isTableBodyContextTag(token->name())) {
1279             // FIXME: This could be more efficient.
1280             if (!m_tree.openElements()->inTableScope(tdTag) && !m_tree.openElements()->inTableScope(thTag)) {
1281                 ASSERT(isParsingFragment());
1282                 parseError(token);
1283                 return;
1284             }
1285             closeTheCell();
1286             processStartTag(token);
1287             return;
1288         }
1289         processStartTagForInBody(token);
1290         break;
1291     case AfterBodyMode:
1292     case AfterAfterBodyMode:
1293         ASSERT(insertionMode() == AfterBodyMode || insertionMode() == AfterAfterBodyMode);
1294         if (token->name() == htmlTag) {
1295             processHtmlStartTagForInBody(token);
1296             return;
1297         }
1298         setInsertionMode(InBodyMode);
1299         processStartTag(token);
1300         break;
1301     case InHeadNoscriptMode:
1302         ASSERT(insertionMode() == InHeadNoscriptMode);
1303         if (token->name() == htmlTag) {
1304             processHtmlStartTagForInBody(token);
1305             return;
1306         }
1307         if (token->name() == basefontTag
1308             || token->name() == bgsoundTag
1309             || token->name() == linkTag
1310             || token->name() == metaTag
1311             || token->name() == noframesTag
1312             || token->name() == styleTag) {
1313             bool didProcess = processStartTagForInHead(token);
1314             ASSERT_UNUSED(didProcess, didProcess);
1315             return;
1316         }
1317         if (token->name() == htmlTag || token->name() == noscriptTag) {
1318             parseError(token);
1319             return;
1320         }
1321         defaultForInHeadNoscript();
1322         processToken(token);
1323         break;
1324     case InFramesetMode:
1325         ASSERT(insertionMode() == InFramesetMode);
1326         if (token->name() == htmlTag) {
1327             processHtmlStartTagForInBody(token);
1328             return;
1329         }
1330         if (token->name() == framesetTag) {
1331             m_tree.insertHTMLElement(token);
1332             return;
1333         }
1334         if (token->name() == frameTag) {
1335             m_tree.insertSelfClosingHTMLElement(token);
1336             return;
1337         }
1338         if (token->name() == noframesTag) {
1339             processStartTagForInHead(token);
1340             return;
1341         }
1342 #if ENABLE(TEMPLATE_ELEMENT)
1343         if (token->name() == templateTag) {
1344             processTemplateStartTag(token);
1345             return;
1346         }
1347 #endif
1348         parseError(token);
1349         break;
1350     case AfterFramesetMode:
1351     case AfterAfterFramesetMode:
1352         ASSERT(insertionMode() == AfterFramesetMode || insertionMode() == AfterAfterFramesetMode);
1353         if (token->name() == htmlTag) {
1354             processHtmlStartTagForInBody(token);
1355             return;
1356         }
1357         if (token->name() == noframesTag) {
1358             processStartTagForInHead(token);
1359             return;
1360         }
1361         parseError(token);
1362         break;
1363     case InSelectInTableMode:
1364         ASSERT(insertionMode() == InSelectInTableMode);
1365         if (token->name() == captionTag
1366             || token->name() == tableTag
1367             || isTableBodyContextTag(token->name())
1368             || token->name() == trTag
1369             || isTableCellContextTag(token->name())) {
1370             parseError(token);
1371             AtomicHTMLToken endSelect(HTMLToken::EndTag, selectTag.localName());
1372             processEndTag(&endSelect);
1373             processStartTag(token);
1374             return;
1375         }
1376         // Fall through
1377     case InSelectMode:
1378         ASSERT(insertionMode() == InSelectMode || insertionMode() == InSelectInTableMode);
1379         if (token->name() == htmlTag) {
1380             processHtmlStartTagForInBody(token);
1381             return;
1382         }
1383         if (token->name() == optionTag) {
1384             if (m_tree.currentStackItem()->hasTagName(optionTag)) {
1385                 AtomicHTMLToken endOption(HTMLToken::EndTag, optionTag.localName());
1386                 processEndTag(&endOption);
1387             }
1388             m_tree.insertHTMLElement(token);
1389             return;
1390         }
1391         if (token->name() == optgroupTag) {
1392             if (m_tree.currentStackItem()->hasTagName(optionTag)) {
1393                 AtomicHTMLToken endOption(HTMLToken::EndTag, optionTag.localName());
1394                 processEndTag(&endOption);
1395             }
1396             if (m_tree.currentStackItem()->hasTagName(optgroupTag)) {
1397                 AtomicHTMLToken endOptgroup(HTMLToken::EndTag, optgroupTag.localName());
1398                 processEndTag(&endOptgroup);
1399             }
1400             m_tree.insertHTMLElement(token);
1401             return;
1402         }
1403         if (token->name() == selectTag) {
1404             parseError(token);
1405             AtomicHTMLToken endSelect(HTMLToken::EndTag, selectTag.localName());
1406             processEndTag(&endSelect);
1407             return;
1408         }
1409         if (token->name() == inputTag
1410             || token->name() == keygenTag
1411             || token->name() == textareaTag) {
1412             parseError(token);
1413             if (!m_tree.openElements()->inSelectScope(selectTag)) {
1414                 ASSERT(isParsingFragment());
1415                 return;
1416             }
1417             AtomicHTMLToken endSelect(HTMLToken::EndTag, selectTag.localName());
1418             processEndTag(&endSelect);
1419             processStartTag(token);
1420             return;
1421         }
1422         if (token->name() == scriptTag) {
1423             bool didProcess = processStartTagForInHead(token);
1424             ASSERT_UNUSED(didProcess, didProcess);
1425             return;
1426         }
1427 #if ENABLE(TEMPLATE_ELEMENT)
1428         if (token->name() == templateTag) {
1429             processTemplateStartTag(token);
1430             return;
1431         }
1432 #endif
1433         break;
1434     case InTableTextMode:
1435         defaultForInTableText();
1436         processStartTag(token);
1437         break;
1438     case TextMode:
1439         ASSERT_NOT_REACHED();
1440         break;
1441     case TemplateContentsMode:
1442 #if ENABLE(TEMPLATE_ELEMENT)
1443         if (token->name() == templateTag) {
1444             processTemplateStartTag(token);
1445             return;
1446         }
1447
1448         if (token->name() == linkTag
1449             || token->name() == scriptTag
1450             || token->name() == styleTag
1451             || token->name() == metaTag) {
1452             processStartTagForInHead(token);
1453             return;
1454         }
1455
1456         InsertionMode insertionMode = TemplateContentsMode;
1457         if (token->name() == frameTag)
1458             insertionMode = InFramesetMode;
1459         else if (token->name() == colTag)
1460             insertionMode = InColumnGroupMode;
1461         else if (isCaptionColOrColgroupTag(token->name()) || isTableBodyContextTag(token->name()))
1462             insertionMode = InTableMode;
1463         else if (token->name() == trTag)
1464             insertionMode = InTableBodyMode;
1465         else if (isTableCellContextTag(token->name()))
1466             insertionMode = InRowMode;
1467         else
1468             insertionMode = InBodyMode;
1469
1470         ASSERT(insertionMode != TemplateContentsMode);
1471         ASSERT(m_templateInsertionModes.last() == TemplateContentsMode);
1472         m_templateInsertionModes.last() = insertionMode;
1473         setInsertionMode(insertionMode);
1474
1475         processStartTag(token);
1476 #else
1477         ASSERT_NOT_REACHED();
1478 #endif
1479         break;
1480     }
1481 }
1482
1483 void HTMLTreeBuilder::processHtmlStartTagForInBody(AtomicHTMLToken* token)
1484 {
1485     parseError(token);
1486 #if ENABLE(TEMPLATE_ELEMENT)
1487     if (m_tree.openElements()->hasTemplateInHTMLScope()) {
1488         ASSERT(isParsingTemplateContents());
1489         return;
1490     }
1491 #endif
1492     m_tree.insertHTMLHtmlStartTagInBody(token);
1493 }
1494
1495 bool HTMLTreeBuilder::processBodyEndTagForInBody(AtomicHTMLToken* token)
1496 {
1497     ASSERT(token->type() == HTMLToken::EndTag);
1498     ASSERT(token->name() == bodyTag);
1499     if (!m_tree.openElements()->inScope(bodyTag.localName())) {
1500         parseError(token);
1501         return false;
1502     }
1503     notImplemented(); // Emit a more specific parse error based on stack contents.
1504     setInsertionMode(AfterBodyMode);
1505     return true;
1506 }
1507
1508 void HTMLTreeBuilder::processAnyOtherEndTagForInBody(AtomicHTMLToken* token)
1509 {
1510     ASSERT(token->type() == HTMLToken::EndTag);
1511     HTMLElementStack::ElementRecord* record = m_tree.openElements()->topRecord();
1512     while (1) {
1513         RefPtr<HTMLStackItem> item = record->stackItem();
1514         if (item->hasLocalName(token->name())) {
1515             m_tree.generateImpliedEndTagsWithExclusion(token->name());
1516             if (!m_tree.currentStackItem()->hasLocalName(token->name()))
1517                 parseError(token);
1518             m_tree.openElements()->popUntilPopped(item->element());
1519             return;
1520         }
1521         if (item->isSpecialNode()) {
1522             parseError(token);
1523             return;
1524         }
1525         record = record->next();
1526     }
1527 }
1528
1529 // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#parsing-main-inbody
1530 void HTMLTreeBuilder::callTheAdoptionAgency(AtomicHTMLToken* token)
1531 {
1532     // The adoption agency algorithm is N^2. We limit the number of iterations
1533     // to stop from hanging the whole browser. This limit is specified in the
1534     // adoption agency algorithm:
1535     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tree-construction.html#parsing-main-inbody
1536     static const int outerIterationLimit = 8;
1537     static const int innerIterationLimit = 3;
1538
1539     // 1, 2, 3 and 16 are covered by the for() loop.
1540     for (int i = 0; i < outerIterationLimit; ++i) {
1541         // 4.
1542         Element* formattingElement = m_tree.activeFormattingElements()->closestElementInScopeWithName(token->name());
1543         // 4.a
1544         if (!formattingElement)
1545             return processAnyOtherEndTagForInBody(token);
1546         // 4.c
1547         if ((m_tree.openElements()->contains(formattingElement)) && !m_tree.openElements()->inScope(formattingElement)) {
1548             parseError(token);
1549             notImplemented(); // Check the stack of open elements for a more specific parse error.
1550             return;
1551         }
1552         // 4.b
1553         HTMLElementStack::ElementRecord* formattingElementRecord = m_tree.openElements()->find(formattingElement);
1554         if (!formattingElementRecord) {
1555             parseError(token);
1556             m_tree.activeFormattingElements()->remove(formattingElement);
1557             return;
1558         }
1559         // 4.d
1560         if (formattingElement != m_tree.currentElement())
1561             parseError(token);
1562         // 5.
1563         HTMLElementStack::ElementRecord* furthestBlock = m_tree.openElements()->furthestBlockForFormattingElement(formattingElement);
1564         // 6.
1565         if (!furthestBlock) {
1566             m_tree.openElements()->popUntilPopped(formattingElement);
1567             m_tree.activeFormattingElements()->remove(formattingElement);
1568             return;
1569         }
1570         // 7.
1571         ASSERT(furthestBlock->isAbove(formattingElementRecord));
1572         RefPtr<HTMLStackItem> commonAncestor = formattingElementRecord->next()->stackItem();
1573         // 8.
1574         HTMLFormattingElementList::Bookmark bookmark = m_tree.activeFormattingElements()->bookmarkFor(formattingElement);
1575         // 9.
1576         HTMLElementStack::ElementRecord* node = furthestBlock;
1577         HTMLElementStack::ElementRecord* nextNode = node->next();
1578         HTMLElementStack::ElementRecord* lastNode = furthestBlock;
1579         // 9.1, 9.2, 9.3 and 9.11 are covered by the for() loop.
1580         for (int i = 0; i < innerIterationLimit; ++i) {
1581             // 9.4
1582             node = nextNode;
1583             ASSERT(node);
1584             nextNode = node->next(); // Save node->next() for the next iteration in case node is deleted in 9.5.
1585             // 9.5
1586             if (!m_tree.activeFormattingElements()->contains(node->element())) {
1587                 m_tree.openElements()->remove(node->element());
1588                 node = 0;
1589                 continue;
1590             }
1591             // 9.6
1592             if (node == formattingElementRecord)
1593                 break;
1594             // 9.7
1595             RefPtr<HTMLStackItem> newItem = m_tree.createElementFromSavedToken(node->stackItem().get());
1596
1597             HTMLFormattingElementList::Entry* nodeEntry = m_tree.activeFormattingElements()->find(node->element());
1598             nodeEntry->replaceElement(newItem);
1599             node->replaceElement(newItem.release());
1600
1601             // 9.8
1602             if (lastNode == furthestBlock)
1603                 bookmark.moveToAfter(nodeEntry);
1604             // 9.9
1605             if (ContainerNode* parent = lastNode->element()->parentNode())
1606                 parent->parserRemoveChild(lastNode->element());
1607             node->element()->parserAppendChild(lastNode->element());
1608             if (lastNode->element()->parentElement()->attached() && !lastNode->element()->attached())
1609                 lastNode->element()->lazyAttach();
1610             // 9.10
1611             lastNode = node;
1612         }
1613         // 10.
1614         if (ContainerNode* parent = lastNode->element()->parentNode())
1615             parent->parserRemoveChild(lastNode->element());
1616         if (commonAncestor->causesFosterParenting())
1617             m_tree.fosterParent(lastNode->element());
1618         else {
1619 #if ENABLE(TEMPLATE_ELEMENT)
1620             if (commonAncestor->hasTagName(templateTag))
1621                 toHTMLTemplateElement(commonAncestor->node())->content()->parserAppendChild(lastNode->element());
1622             else
1623                 commonAncestor->node()->parserAppendChild(lastNode->element());
1624 #else
1625             commonAncestor->node()->parserAppendChild(lastNode->element());
1626 #endif
1627             ASSERT(lastNode->stackItem()->isElementNode());
1628             ASSERT(lastNode->element()->parentNode());
1629             if (lastNode->element()->parentNode()->attached() && !lastNode->element()->attached())
1630                 lastNode->element()->lazyAttach();
1631         }
1632         // 11.
1633         RefPtr<HTMLStackItem> newItem = m_tree.createElementFromSavedToken(formattingElementRecord->stackItem().get());
1634         // 12.
1635         newItem->element()->takeAllChildrenFrom(furthestBlock->element());
1636         // 13.
1637         Element* furthestBlockElement = furthestBlock->element();
1638         // FIXME: All this creation / parserAppendChild / attach business should
1639         //        be in HTMLConstructionSite. My guess is that steps 11--15
1640         //        should all be in some HTMLConstructionSite function.
1641         furthestBlockElement->parserAppendChild(newItem->element());
1642         // FIXME: Why is this attach logic necessary? Style resolve should attach us if needed.
1643         if (furthestBlockElement->attached() && !newItem->element()->attached()) {
1644             // Notice that newItem->element() might already be attached if, for example, one of the reparented
1645             // children is a style element, which attaches itself automatically.
1646             newItem->element()->attach();
1647         }
1648         // 14.
1649         m_tree.activeFormattingElements()->swapTo(formattingElement, newItem, bookmark);
1650         // 15.
1651         m_tree.openElements()->remove(formattingElement);
1652         m_tree.openElements()->insertAbove(newItem, furthestBlock);
1653     }
1654 }
1655
1656 void HTMLTreeBuilder::resetInsertionModeAppropriately()
1657 {
1658     // http://www.whatwg.org/specs/web-apps/current-work/multipage/parsing.html#reset-the-insertion-mode-appropriately
1659     bool last = false;
1660     HTMLElementStack::ElementRecord* nodeRecord = m_tree.openElements()->topRecord();
1661     while (1) {
1662         RefPtr<HTMLStackItem> item = nodeRecord->stackItem();
1663         if (item->node() == m_tree.openElements()->rootNode()) {
1664             ASSERT(isParsingFragment());
1665             last = true;
1666             item = HTMLStackItem::create(m_fragmentContext.contextElement(), HTMLStackItem::ItemForContextElement);
1667         }
1668 #if ENABLE(TEMPLATE_ELEMENT)
1669         if (item->hasTagName(templateTag))
1670             return setInsertionMode(m_templateInsertionModes.last());
1671 #endif
1672         if (item->hasTagName(selectTag)) {
1673             return setInsertionMode(InSelectMode);
1674         }
1675         if (item->hasTagName(tdTag) || item->hasTagName(thTag))
1676             return setInsertionMode(InCellMode);
1677         if (item->hasTagName(trTag))
1678             return setInsertionMode(InRowMode);
1679         if (item->hasTagName(tbodyTag) || item->hasTagName(theadTag) || item->hasTagName(tfootTag))
1680             return setInsertionMode(InTableBodyMode);
1681         if (item->hasTagName(captionTag))
1682             return setInsertionMode(InCaptionMode);
1683         if (item->hasTagName(colgroupTag)) {
1684             return setInsertionMode(InColumnGroupMode);
1685         }
1686         if (item->hasTagName(tableTag))
1687             return setInsertionMode(InTableMode);
1688         if (item->hasTagName(headTag)) {
1689 #if ENABLE(TEMPLATE_ELEMENT)
1690             if (!m_fragmentContext.fragment() || m_fragmentContext.contextElement() != item->node())
1691                 return setInsertionMode(InHeadMode);
1692 #endif
1693             return setInsertionMode(InBodyMode);
1694         }
1695         if (item->hasTagName(bodyTag))
1696             return setInsertionMode(InBodyMode);
1697         if (item->hasTagName(framesetTag)) {
1698             return setInsertionMode(InFramesetMode);
1699         }
1700         if (item->hasTagName(htmlTag)) {
1701             ASSERT(isParsingFragment());
1702             return setInsertionMode(BeforeHeadMode);
1703         }
1704         if (last) {
1705             ASSERT(isParsingFragment());
1706             return setInsertionMode(InBodyMode);
1707         }
1708         nodeRecord = nodeRecord->next();
1709     }
1710 }
1711
1712 void HTMLTreeBuilder::processEndTagForInTableBody(AtomicHTMLToken* token)
1713 {
1714     ASSERT(token->type() == HTMLToken::EndTag);
1715     if (isTableBodyContextTag(token->name())) {
1716         if (!m_tree.openElements()->inTableScope(token->name())) {
1717             parseError(token);
1718             return;
1719         }
1720         m_tree.openElements()->popUntilTableBodyScopeMarker();
1721         m_tree.openElements()->pop();
1722         setInsertionMode(InTableMode);
1723         return;
1724     }
1725     if (token->name() == tableTag) {
1726         // FIXME: This is slow.
1727         if (!m_tree.openElements()->inTableScope(tbodyTag) && !m_tree.openElements()->inTableScope(theadTag) && !m_tree.openElements()->inTableScope(tfootTag)) {
1728             ASSERT(isParsingFragmentOrTemplateContents());
1729             parseError(token);
1730             return;
1731         }
1732         m_tree.openElements()->popUntilTableBodyScopeMarker();
1733         ASSERT(isTableBodyContextTag(m_tree.currentStackItem()->localName()));
1734         processFakeEndTag(m_tree.currentStackItem()->localName());
1735         processEndTag(token);
1736         return;
1737     }
1738     if (token->name() == bodyTag
1739         || isCaptionColOrColgroupTag(token->name())
1740         || token->name() == htmlTag
1741         || isTableCellContextTag(token->name())
1742         || token->name() == trTag) {
1743         parseError(token);
1744         return;
1745     }
1746     processEndTagForInTable(token);
1747 }
1748
1749 void HTMLTreeBuilder::processEndTagForInRow(AtomicHTMLToken* token)
1750 {
1751     ASSERT(token->type() == HTMLToken::EndTag);
1752     if (token->name() == trTag) {
1753         processTrEndTagForInRow();
1754         return;
1755     }
1756     if (token->name() == tableTag) {
1757         if (!processTrEndTagForInRow()) {
1758             ASSERT(isParsingFragmentOrTemplateContents());
1759             return;
1760         }
1761         ASSERT(insertionMode() == InTableBodyMode);
1762         processEndTag(token);
1763         return;
1764     }
1765     if (isTableBodyContextTag(token->name())) {
1766         if (!m_tree.openElements()->inTableScope(token->name())) {
1767             parseError(token);
1768             return;
1769         }
1770         processFakeEndTag(trTag);
1771         ASSERT(insertionMode() == InTableBodyMode);
1772         processEndTag(token);
1773         return;
1774     }
1775     if (token->name() == bodyTag
1776         || isCaptionColOrColgroupTag(token->name())
1777         || token->name() == htmlTag
1778         || isTableCellContextTag(token->name())) {
1779         parseError(token);
1780         return;
1781     }
1782     processEndTagForInTable(token);
1783 }
1784
1785 void HTMLTreeBuilder::processEndTagForInCell(AtomicHTMLToken* token)
1786 {
1787     ASSERT(token->type() == HTMLToken::EndTag);
1788     if (isTableCellContextTag(token->name())) {
1789         if (!m_tree.openElements()->inTableScope(token->name())) {
1790             parseError(token);
1791             return;
1792         }
1793         m_tree.generateImpliedEndTags();
1794         if (!m_tree.currentStackItem()->hasLocalName(token->name()))
1795             parseError(token);
1796         m_tree.openElements()->popUntilPopped(token->name());
1797         m_tree.activeFormattingElements()->clearToLastMarker();
1798         setInsertionMode(InRowMode);
1799         return;
1800     }
1801     if (token->name() == bodyTag
1802         || isCaptionColOrColgroupTag(token->name())
1803         || token->name() == htmlTag) {
1804         parseError(token);
1805         return;
1806     }
1807     if (token->name() == tableTag
1808         || token->name() == trTag
1809         || isTableBodyContextTag(token->name())) {
1810         if (!m_tree.openElements()->inTableScope(token->name())) {
1811 #if ENABLE(TEMPLATE_ELEMENT)
1812             ASSERT(isTableBodyContextTag(token->name()) || m_tree.openElements()->inTableScope(templateTag) || isParsingFragment());
1813 #else
1814             ASSERT(isTableBodyContextTag(token->name()) || isParsingFragment());
1815 #endif
1816             parseError(token);
1817             return;
1818         }
1819         closeTheCell();
1820         processEndTag(token);
1821         return;
1822     }
1823     processEndTagForInBody(token);
1824 }
1825
1826 void HTMLTreeBuilder::processEndTagForInBody(AtomicHTMLToken* token)
1827 {
1828     ASSERT(token->type() == HTMLToken::EndTag);
1829     if (token->name() == bodyTag) {
1830         processBodyEndTagForInBody(token);
1831         return;
1832     }
1833     if (token->name() == htmlTag) {
1834         AtomicHTMLToken endBody(HTMLToken::EndTag, bodyTag.localName());
1835         if (processBodyEndTagForInBody(&endBody))
1836             processEndTag(token);
1837         return;
1838     }
1839     if (token->name() == addressTag
1840         || token->name() == articleTag
1841         || token->name() == asideTag
1842         || token->name() == blockquoteTag
1843         || token->name() == buttonTag
1844         || token->name() == centerTag
1845         || token->name() == detailsTag
1846         || token->name() == dirTag
1847         || token->name() == divTag
1848         || token->name() == dlTag
1849         || token->name() == fieldsetTag
1850         || token->name() == figcaptionTag
1851         || token->name() == figureTag
1852         || token->name() == footerTag
1853         || token->name() == headerTag
1854         || token->name() == hgroupTag
1855         || token->name() == listingTag
1856         || token->name() == mainTag
1857         || token->name() == menuTag
1858         || token->name() == navTag
1859         || token->name() == olTag
1860         || token->name() == preTag
1861         || token->name() == sectionTag
1862         || token->name() == summaryTag
1863         || token->name() == ulTag) {
1864         if (!m_tree.openElements()->inScope(token->name())) {
1865             parseError(token);
1866             return;
1867         }
1868         m_tree.generateImpliedEndTags();
1869         if (!m_tree.currentStackItem()->hasLocalName(token->name()))
1870             parseError(token);
1871         m_tree.openElements()->popUntilPopped(token->name());
1872         return;
1873     }
1874     if (token->name() == formTag) {
1875         RefPtr<Element> node = m_tree.takeForm();
1876         if (!node || !m_tree.openElements()->inScope(node.get())) {
1877             parseError(token);
1878             return;
1879         }
1880         m_tree.generateImpliedEndTags();
1881         if (m_tree.currentElement() != node.get())
1882             parseError(token);
1883         m_tree.openElements()->remove(node.get());
1884     }
1885     if (token->name() == pTag) {
1886         if (!m_tree.openElements()->inButtonScope(token->name())) {
1887             parseError(token);
1888             processFakeStartTag(pTag);
1889             ASSERT(m_tree.openElements()->inScope(token->name()));
1890             processEndTag(token);
1891             return;
1892         }
1893         m_tree.generateImpliedEndTagsWithExclusion(token->name());
1894         if (!m_tree.currentStackItem()->hasLocalName(token->name()))
1895             parseError(token);
1896         m_tree.openElements()->popUntilPopped(token->name());
1897         return;
1898     }
1899     if (token->name() == liTag) {
1900         if (!m_tree.openElements()->inListItemScope(token->name())) {
1901             parseError(token);
1902             return;
1903         }
1904         m_tree.generateImpliedEndTagsWithExclusion(token->name());
1905         if (!m_tree.currentStackItem()->hasLocalName(token->name()))
1906             parseError(token);
1907         m_tree.openElements()->popUntilPopped(token->name());
1908         return;
1909     }
1910     if (token->name() == ddTag
1911         || token->name() == dtTag) {
1912         if (!m_tree.openElements()->inScope(token->name())) {
1913             parseError(token);
1914             return;
1915         }
1916         m_tree.generateImpliedEndTagsWithExclusion(token->name());
1917         if (!m_tree.currentStackItem()->hasLocalName(token->name()))
1918             parseError(token);
1919         m_tree.openElements()->popUntilPopped(token->name());
1920         return;
1921     }
1922     if (isNumberedHeaderTag(token->name())) {
1923         if (!m_tree.openElements()->hasNumberedHeaderElementInScope()) {
1924             parseError(token);
1925             return;
1926         }
1927         m_tree.generateImpliedEndTags();
1928         if (!m_tree.currentStackItem()->hasLocalName(token->name()))
1929             parseError(token);
1930         m_tree.openElements()->popUntilNumberedHeaderElementPopped();
1931         return;
1932     }
1933     if (isFormattingTag(token->name())) {
1934         callTheAdoptionAgency(token);
1935         return;
1936     }
1937     if (token->name() == appletTag
1938         || token->name() == marqueeTag
1939         || token->name() == objectTag) {
1940         if (!m_tree.openElements()->inScope(token->name())) {
1941             parseError(token);
1942             return;
1943         }
1944         m_tree.generateImpliedEndTags();
1945         if (!m_tree.currentStackItem()->hasLocalName(token->name()))
1946             parseError(token);
1947         m_tree.openElements()->popUntilPopped(token->name());
1948         m_tree.activeFormattingElements()->clearToLastMarker();
1949         return;
1950     }
1951     if (token->name() == brTag) {
1952         parseError(token);
1953         processFakeStartTag(brTag);
1954         return;
1955     }
1956 #if ENABLE(TEMPLATE_ELEMENT)
1957     if (token->name() == templateTag) {
1958         processTemplateEndTag(token);
1959         return;
1960     }
1961 #endif
1962     processAnyOtherEndTagForInBody(token);
1963 }
1964
1965 bool HTMLTreeBuilder::processCaptionEndTagForInCaption()
1966 {
1967     if (!m_tree.openElements()->inTableScope(captionTag.localName())) {
1968         ASSERT(isParsingFragment());
1969         // FIXME: parse error
1970         return false;
1971     }
1972     m_tree.generateImpliedEndTags();
1973     // FIXME: parse error if (!m_tree.currentStackItem()->hasTagName(captionTag))
1974     m_tree.openElements()->popUntilPopped(captionTag.localName());
1975     m_tree.activeFormattingElements()->clearToLastMarker();
1976     setInsertionMode(InTableMode);
1977     return true;
1978 }
1979
1980 bool HTMLTreeBuilder::processTrEndTagForInRow()
1981 {
1982     if (!m_tree.openElements()->inTableScope(trTag)) {
1983         ASSERT(isParsingFragmentOrTemplateContents());
1984         // FIXME: parse error
1985         return false;
1986     }
1987     m_tree.openElements()->popUntilTableRowScopeMarker();
1988     ASSERT(m_tree.currentStackItem()->hasTagName(trTag));
1989     m_tree.openElements()->pop();
1990     setInsertionMode(InTableBodyMode);
1991     return true;
1992 }
1993
1994 bool HTMLTreeBuilder::processTableEndTagForInTable()
1995 {
1996     if (!m_tree.openElements()->inTableScope(tableTag)) {
1997         ASSERT(isParsingFragmentOrTemplateContents());
1998         // FIXME: parse error.
1999         return false;
2000     }
2001     m_tree.openElements()->popUntilPopped(tableTag.localName());
2002     resetInsertionModeAppropriately();
2003     return true;
2004 }
2005
2006 void HTMLTreeBuilder::processEndTagForInTable(AtomicHTMLToken* token)
2007 {
2008     ASSERT(token->type() == HTMLToken::EndTag);
2009     if (token->name() == tableTag) {
2010         processTableEndTagForInTable();
2011         return;
2012     }
2013     if (token->name() == bodyTag
2014         || isCaptionColOrColgroupTag(token->name())
2015         || token->name() == htmlTag
2016         || isTableBodyContextTag(token->name())
2017         || isTableCellContextTag(token->name())
2018         || token->name() == trTag) {
2019         parseError(token);
2020         return;
2021     }
2022     parseError(token);
2023     // Is this redirection necessary here?
2024     HTMLConstructionSite::RedirectToFosterParentGuard redirecter(m_tree);
2025     processEndTagForInBody(token);
2026 }
2027
2028 void HTMLTreeBuilder::processEndTag(AtomicHTMLToken* token)
2029 {
2030     ASSERT(token->type() == HTMLToken::EndTag);
2031     switch (insertionMode()) {
2032     case InitialMode:
2033         ASSERT(insertionMode() == InitialMode);
2034         defaultForInitial();
2035         // Fall through.
2036     case BeforeHTMLMode:
2037         ASSERT(insertionMode() == BeforeHTMLMode);
2038         if (token->name() != headTag && token->name() != bodyTag && token->name() != htmlTag && token->name() != brTag) {
2039             parseError(token);
2040             return;
2041         }
2042         defaultForBeforeHTML();
2043         // Fall through.
2044     case BeforeHeadMode:
2045         ASSERT(insertionMode() == BeforeHeadMode);
2046         if (token->name() != headTag && token->name() != bodyTag && token->name() != htmlTag && token->name() != brTag) {
2047             parseError(token);
2048             return;
2049         }
2050         defaultForBeforeHead();
2051         // Fall through.
2052     case InHeadMode:
2053         ASSERT(insertionMode() == InHeadMode);
2054         // FIXME: This case should be broken out into processEndTagForInHead,
2055         // because other end tag cases now refer to it ("process the token for using the rules of the "in head" insertion mode").
2056         // but because the logic falls through to AfterHeadMode, that gets a little messy.
2057 #if ENABLE(TEMPLATE_ELEMENT)
2058         if (token->name() == templateTag) {
2059             processTemplateEndTag(token);
2060             return;
2061         }
2062 #endif
2063         if (token->name() == headTag) {
2064             m_tree.openElements()->popHTMLHeadElement();
2065             setInsertionMode(AfterHeadMode);
2066             return;
2067         }
2068         if (token->name() != bodyTag && token->name() != htmlTag && token->name() != brTag) {
2069             parseError(token);
2070             return;
2071         }
2072         defaultForInHead();
2073         // Fall through.
2074     case AfterHeadMode:
2075         ASSERT(insertionMode() == AfterHeadMode);
2076         if (token->name() != bodyTag && token->name() != htmlTag && token->name() != brTag) {
2077             parseError(token);
2078             return;
2079         }
2080         defaultForAfterHead();
2081         // Fall through
2082     case InBodyMode:
2083         ASSERT(insertionMode() == InBodyMode);
2084         processEndTagForInBody(token);
2085         break;
2086     case InTableMode:
2087         ASSERT(insertionMode() == InTableMode);
2088         processEndTagForInTable(token);
2089         break;
2090     case InCaptionMode:
2091         ASSERT(insertionMode() == InCaptionMode);
2092         if (token->name() == captionTag) {
2093             processCaptionEndTagForInCaption();
2094             return;
2095         }
2096         if (token->name() == tableTag) {
2097             parseError(token);
2098             if (!processCaptionEndTagForInCaption()) {
2099                 ASSERT(isParsingFragment());
2100                 return;
2101             }
2102             processEndTag(token);
2103             return;
2104         }
2105         if (token->name() == bodyTag
2106             || token->name() == colTag
2107             || token->name() == colgroupTag
2108             || token->name() == htmlTag
2109             || isTableBodyContextTag(token->name())
2110             || isTableCellContextTag(token->name())
2111             || token->name() == trTag) {
2112             parseError(token);
2113             return;
2114         }
2115         processEndTagForInBody(token);
2116         break;
2117     case InColumnGroupMode:
2118         ASSERT(insertionMode() == InColumnGroupMode);
2119         if (token->name() == colgroupTag) {
2120             processColgroupEndTagForInColumnGroup();
2121             return;
2122         }
2123         if (token->name() == colTag) {
2124             parseError(token);
2125             return;
2126         }
2127 #if ENABLE(TEMPLATE_ELEMENT)
2128         if (token->name() == templateTag) {
2129             processTemplateEndTag(token);
2130             return;
2131         }
2132 #endif
2133         if (!processColgroupEndTagForInColumnGroup()) {
2134             ASSERT(isParsingFragmentOrTemplateContents());
2135             return;
2136         }
2137         processEndTag(token);
2138         break;
2139     case InRowMode:
2140         ASSERT(insertionMode() == InRowMode);
2141         processEndTagForInRow(token);
2142         break;
2143     case InCellMode:
2144         ASSERT(insertionMode() == InCellMode);
2145         processEndTagForInCell(token);
2146         break;
2147     case InTableBodyMode:
2148         ASSERT(insertionMode() == InTableBodyMode);
2149         processEndTagForInTableBody(token);
2150         break;
2151     case AfterBodyMode:
2152         ASSERT(insertionMode() == AfterBodyMode);
2153         if (token->name() == htmlTag) {
2154             if (isParsingFragment()) {
2155                 parseError(token);
2156                 return;
2157             }
2158             setInsertionMode(AfterAfterBodyMode);
2159             return;
2160         }
2161         // Fall through.
2162     case AfterAfterBodyMode:
2163         ASSERT(insertionMode() == AfterBodyMode || insertionMode() == AfterAfterBodyMode);
2164         parseError(token);
2165         setInsertionMode(InBodyMode);
2166         processEndTag(token);
2167         break;
2168     case InHeadNoscriptMode:
2169         ASSERT(insertionMode() == InHeadNoscriptMode);
2170         if (token->name() == noscriptTag) {
2171             ASSERT(m_tree.currentStackItem()->hasTagName(noscriptTag));
2172             m_tree.openElements()->pop();
2173             ASSERT(m_tree.currentStackItem()->hasTagName(headTag));
2174             setInsertionMode(InHeadMode);
2175             return;
2176         }
2177         if (token->name() != brTag) {
2178             parseError(token);
2179             return;
2180         }
2181         defaultForInHeadNoscript();
2182         processToken(token);
2183         break;
2184     case TextMode:
2185         if (token->name() == scriptTag) {
2186             // Pause ourselves so that parsing stops until the script can be processed by the caller.
2187             ASSERT(m_tree.currentStackItem()->hasTagName(scriptTag));
2188             m_scriptToProcess = m_tree.currentElement();
2189             m_tree.openElements()->pop();
2190             if (isParsingFragment() && !scriptingContentIsAllowed(m_fragmentContext.scriptingPermission()))
2191                 m_scriptToProcess->removeChildren();
2192             setInsertionMode(m_originalInsertionMode);
2193
2194             if (m_parser->tokenizer()) {
2195                 // This token will not have been created by the tokenizer if a
2196                 // self-closing script tag was encountered and pre-HTML5 parser
2197                 // quirks are enabled. We must set the tokenizer's state to
2198                 // DataState explicitly if the tokenizer didn't have a chance to.
2199                 ASSERT(m_parser->tokenizer()->state() == HTMLTokenizer::DataState || m_options.usePreHTML5ParserQuirks || m_options.useThreading);
2200                 m_parser->tokenizer()->setState(HTMLTokenizer::DataState);
2201             }
2202             return;
2203         }
2204         m_tree.openElements()->pop();
2205         setInsertionMode(m_originalInsertionMode);
2206         break;
2207     case InFramesetMode:
2208         ASSERT(insertionMode() == InFramesetMode);
2209         if (token->name() == framesetTag) {
2210             bool ignoreFramesetForFragmentParsing  = m_tree.currentIsRootNode();
2211 #if ENABLE(TEMPLATE_ELEMENT)
2212             ignoreFramesetForFragmentParsing = ignoreFramesetForFragmentParsing || m_tree.openElements()->hasTemplateInHTMLScope();
2213 #endif
2214             if (ignoreFramesetForFragmentParsing) {
2215                 ASSERT(isParsingFragmentOrTemplateContents());
2216                 parseError(token);
2217                 return;
2218             }
2219             m_tree.openElements()->pop();
2220             if (!isParsingFragment() && !m_tree.currentStackItem()->hasTagName(framesetTag))
2221                 setInsertionMode(AfterFramesetMode);
2222             return;
2223         }
2224 #if ENABLE(TEMPLATE_ELEMENT)
2225         if (token->name() == templateTag) {
2226             processTemplateEndTag(token);
2227             return;
2228         }
2229 #endif
2230         break;
2231     case AfterFramesetMode:
2232         ASSERT(insertionMode() == AfterFramesetMode);
2233         if (token->name() == htmlTag) {
2234             setInsertionMode(AfterAfterFramesetMode);
2235             return;
2236         }
2237         // Fall through.
2238     case AfterAfterFramesetMode:
2239         ASSERT(insertionMode() == AfterFramesetMode || insertionMode() == AfterAfterFramesetMode);
2240         parseError(token);
2241         break;
2242     case InSelectInTableMode:
2243         ASSERT(insertionMode() == InSelectInTableMode);
2244         if (token->name() == captionTag
2245             || token->name() == tableTag
2246             || isTableBodyContextTag(token->name())
2247             || token->name() == trTag
2248             || isTableCellContextTag(token->name())) {
2249             parseError(token);
2250             if (m_tree.openElements()->inTableScope(token->name())) {
2251                 AtomicHTMLToken endSelect(HTMLToken::EndTag, selectTag.localName());
2252                 processEndTag(&endSelect);
2253                 processEndTag(token);
2254             }
2255             return;
2256         }
2257         // Fall through.
2258     case InSelectMode:
2259         ASSERT(insertionMode() == InSelectMode || insertionMode() == InSelectInTableMode);
2260         if (token->name() == optgroupTag) {
2261             if (m_tree.currentStackItem()->hasTagName(optionTag) && m_tree.oneBelowTop() && m_tree.oneBelowTop()->hasTagName(optgroupTag))
2262                 processFakeEndTag(optionTag);
2263             if (m_tree.currentStackItem()->hasTagName(optgroupTag)) {
2264                 m_tree.openElements()->pop();
2265                 return;
2266             }
2267             parseError(token);
2268             return;
2269         }
2270         if (token->name() == optionTag) {
2271             if (m_tree.currentStackItem()->hasTagName(optionTag)) {
2272                 m_tree.openElements()->pop();
2273                 return;
2274             }
2275             parseError(token);
2276             return;
2277         }
2278         if (token->name() == selectTag) {
2279             if (!m_tree.openElements()->inSelectScope(token->name())) {
2280                 ASSERT(isParsingFragment());
2281                 parseError(token);
2282                 return;
2283             }
2284             m_tree.openElements()->popUntilPopped(selectTag.localName());
2285             resetInsertionModeAppropriately();
2286             return;
2287         }
2288 #if ENABLE(TEMPLATE_ELEMENT)
2289         if (token->name() == templateTag) {
2290             processTemplateEndTag(token);
2291             return;
2292         }
2293 #endif
2294         break;
2295     case InTableTextMode:
2296         defaultForInTableText();
2297         processEndTag(token);
2298         break;
2299     case TemplateContentsMode:
2300 #if ENABLE(TEMPLATE_ELEMENT)
2301         if (token->name() == templateTag) {
2302             processTemplateEndTag(token);
2303             return;
2304         }
2305
2306         break;
2307 #else
2308         ASSERT_NOT_REACHED();
2309 #endif
2310         break;
2311     }
2312 }
2313
2314 void HTMLTreeBuilder::processComment(AtomicHTMLToken* token)
2315 {
2316     ASSERT(token->type() == HTMLToken::Comment);
2317     if (m_insertionMode == InitialMode
2318         || m_insertionMode == BeforeHTMLMode
2319         || m_insertionMode == AfterAfterBodyMode
2320         || m_insertionMode == AfterAfterFramesetMode) {
2321         m_tree.insertCommentOnDocument(token);
2322         return;
2323     }
2324     if (m_insertionMode == AfterBodyMode) {
2325         m_tree.insertCommentOnHTMLHtmlElement(token);
2326         return;
2327     }
2328     if (m_insertionMode == InTableTextMode) {
2329         defaultForInTableText();
2330         processComment(token);
2331         return;
2332     }
2333     m_tree.insertComment(token);
2334 }
2335
2336 void HTMLTreeBuilder::processCharacter(AtomicHTMLToken* token)
2337 {
2338     ASSERT(token->type() == HTMLToken::Character);
2339     ExternalCharacterTokenBuffer buffer(token);
2340     processCharacterBuffer(buffer);
2341 }
2342
2343 void HTMLTreeBuilder::processCharacterBuffer(ExternalCharacterTokenBuffer& buffer)
2344 {
2345 ReprocessBuffer:
2346     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#parsing-main-inbody
2347     // Note that this logic is different than the generic \r\n collapsing
2348     // handled in the input stream preprocessor. This logic is here as an
2349     // "authoring convenience" so folks can write:
2350     //
2351     // <pre>
2352     // lorem ipsum
2353     // lorem ipsum
2354     // </pre>
2355     //
2356     // without getting an extra newline at the start of their <pre> element.
2357     if (m_shouldSkipLeadingNewline) {
2358         m_shouldSkipLeadingNewline = false;
2359         buffer.skipAtMostOneLeadingNewline();
2360         if (buffer.isEmpty())
2361             return;
2362     }
2363
2364     switch (insertionMode()) {
2365     case InitialMode: {
2366         ASSERT(insertionMode() == InitialMode);
2367         buffer.skipLeadingWhitespace();
2368         if (buffer.isEmpty())
2369             return;
2370         defaultForInitial();
2371         // Fall through.
2372     }
2373     case BeforeHTMLMode: {
2374         ASSERT(insertionMode() == BeforeHTMLMode);
2375         buffer.skipLeadingWhitespace();
2376         if (buffer.isEmpty())
2377             return;
2378         defaultForBeforeHTML();
2379         // Fall through.
2380     }
2381     case BeforeHeadMode: {
2382         ASSERT(insertionMode() == BeforeHeadMode);
2383         buffer.skipLeadingWhitespace();
2384         if (buffer.isEmpty())
2385             return;
2386         defaultForBeforeHead();
2387         // Fall through.
2388     }
2389     case InHeadMode: {
2390         ASSERT(insertionMode() == InHeadMode);
2391         String leadingWhitespace = buffer.takeLeadingWhitespace();
2392         if (!leadingWhitespace.isEmpty())
2393             m_tree.insertTextNode(leadingWhitespace, AllWhitespace);
2394         if (buffer.isEmpty())
2395             return;
2396         defaultForInHead();
2397         // Fall through.
2398     }
2399     case AfterHeadMode: {
2400         ASSERT(insertionMode() == AfterHeadMode);
2401         String leadingWhitespace = buffer.takeLeadingWhitespace();
2402         if (!leadingWhitespace.isEmpty())
2403             m_tree.insertTextNode(leadingWhitespace, AllWhitespace);
2404         if (buffer.isEmpty())
2405             return;
2406         defaultForAfterHead();
2407         // Fall through.
2408     }
2409     case InBodyMode:
2410     case InCaptionMode:
2411     case TemplateContentsMode:
2412     case InCellMode: {
2413 #if ENABLE(TEMPLATE_ELEMENT)
2414         ASSERT(insertionMode() == InBodyMode || insertionMode() == InCaptionMode || insertionMode() == InCellMode || insertionMode() == TemplateContentsMode);
2415 #else
2416         ASSERT(insertionMode() != TemplateContentsMode);
2417         ASSERT(insertionMode() == InBodyMode || insertionMode() == InCaptionMode || insertionMode() == InCellMode);
2418 #endif
2419         processCharacterBufferForInBody(buffer);
2420         break;
2421     }
2422     case InTableMode:
2423     case InTableBodyMode:
2424     case InRowMode: {
2425         ASSERT(insertionMode() == InTableMode || insertionMode() == InTableBodyMode || insertionMode() == InRowMode);
2426         ASSERT(m_pendingTableCharacters.isEmpty());
2427         if (m_tree.currentStackItem()->isElementNode()
2428             && (m_tree.currentStackItem()->hasTagName(HTMLNames::tableTag)
2429                 || m_tree.currentStackItem()->hasTagName(HTMLNames::tbodyTag)
2430                 || m_tree.currentStackItem()->hasTagName(HTMLNames::tfootTag)
2431                 || m_tree.currentStackItem()->hasTagName(HTMLNames::theadTag)
2432                 || m_tree.currentStackItem()->hasTagName(HTMLNames::trTag))) {
2433             m_originalInsertionMode = m_insertionMode;
2434             setInsertionMode(InTableTextMode);
2435             // Note that we fall through to the InTableTextMode case below.
2436         } else {
2437             HTMLConstructionSite::RedirectToFosterParentGuard redirecter(m_tree);
2438             processCharacterBufferForInBody(buffer);
2439             break;
2440         }
2441         // Fall through.
2442     }
2443     case InTableTextMode: {
2444         buffer.giveRemainingTo(m_pendingTableCharacters);
2445         break;
2446     }
2447     case InColumnGroupMode: {
2448         ASSERT(insertionMode() == InColumnGroupMode);
2449         String leadingWhitespace = buffer.takeLeadingWhitespace();
2450         if (!leadingWhitespace.isEmpty())
2451             m_tree.insertTextNode(leadingWhitespace, AllWhitespace);
2452         if (buffer.isEmpty())
2453             return;
2454         if (!processColgroupEndTagForInColumnGroup()) {
2455             ASSERT(isParsingFragmentOrTemplateContents());
2456             // The spec tells us to drop these characters on the floor.
2457             buffer.skipLeadingNonWhitespace();
2458             if (buffer.isEmpty())
2459                 return;
2460         }
2461         goto ReprocessBuffer;
2462     }
2463     case AfterBodyMode:
2464     case AfterAfterBodyMode: {
2465         ASSERT(insertionMode() == AfterBodyMode || insertionMode() == AfterAfterBodyMode);
2466         // FIXME: parse error
2467         setInsertionMode(InBodyMode);
2468         goto ReprocessBuffer;
2469         break;
2470     }
2471     case TextMode: {
2472         ASSERT(insertionMode() == TextMode);
2473         m_tree.insertTextNode(buffer.takeRemaining());
2474         break;
2475     }
2476     case InHeadNoscriptMode: {
2477         ASSERT(insertionMode() == InHeadNoscriptMode);
2478         String leadingWhitespace = buffer.takeLeadingWhitespace();
2479         if (!leadingWhitespace.isEmpty())
2480             m_tree.insertTextNode(leadingWhitespace, AllWhitespace);
2481         if (buffer.isEmpty())
2482             return;
2483         defaultForInHeadNoscript();
2484         goto ReprocessBuffer;
2485         break;
2486     }
2487     case InFramesetMode:
2488     case AfterFramesetMode: {
2489         ASSERT(insertionMode() == InFramesetMode || insertionMode() == AfterFramesetMode || insertionMode() == AfterAfterFramesetMode);
2490         String leadingWhitespace = buffer.takeRemainingWhitespace();
2491         if (!leadingWhitespace.isEmpty())
2492             m_tree.insertTextNode(leadingWhitespace, AllWhitespace);
2493         // FIXME: We should generate a parse error if we skipped over any
2494         // non-whitespace characters.
2495         break;
2496     }
2497     case InSelectInTableMode:
2498     case InSelectMode: {
2499         ASSERT(insertionMode() == InSelectMode || insertionMode() == InSelectInTableMode);
2500         m_tree.insertTextNode(buffer.takeRemaining());
2501         break;
2502     }
2503     case AfterAfterFramesetMode: {
2504         String leadingWhitespace = buffer.takeRemainingWhitespace();
2505         if (!leadingWhitespace.isEmpty()) {
2506             m_tree.reconstructTheActiveFormattingElements();
2507             m_tree.insertTextNode(leadingWhitespace, AllWhitespace);
2508         }
2509         // FIXME: We should generate a parse error if we skipped over any
2510         // non-whitespace characters.
2511         break;
2512     }
2513     }
2514 }
2515
2516 void HTMLTreeBuilder::processCharacterBufferForInBody(ExternalCharacterTokenBuffer& buffer)
2517 {
2518     m_tree.reconstructTheActiveFormattingElements();
2519     String characters = buffer.takeRemaining();
2520     m_tree.insertTextNode(characters);
2521     if (m_framesetOk && !isAllWhitespaceOrReplacementCharacters(characters))
2522         m_framesetOk = false;
2523 }
2524
2525 void HTMLTreeBuilder::processEndOfFile(AtomicHTMLToken* token)
2526 {
2527     ASSERT(token->type() == HTMLToken::EndOfFile);
2528     switch (insertionMode()) {
2529     case InitialMode:
2530         ASSERT(insertionMode() == InitialMode);
2531         defaultForInitial();
2532         // Fall through.
2533     case BeforeHTMLMode:
2534         ASSERT(insertionMode() == BeforeHTMLMode);
2535         defaultForBeforeHTML();
2536         // Fall through.
2537     case BeforeHeadMode:
2538         ASSERT(insertionMode() == BeforeHeadMode);
2539         defaultForBeforeHead();
2540         // Fall through.
2541     case InHeadMode:
2542         ASSERT(insertionMode() == InHeadMode);
2543         defaultForInHead();
2544         // Fall through.
2545     case AfterHeadMode:
2546         ASSERT(insertionMode() == AfterHeadMode);
2547         defaultForAfterHead();
2548         // Fall through
2549     case InBodyMode:
2550     case InCellMode:
2551     case InCaptionMode:
2552     case InRowMode:
2553 #if ENABLE(TEMPLATE_ELEMENT)
2554         ASSERT(insertionMode() == InBodyMode || insertionMode() == InCellMode || insertionMode() == InCaptionMode || insertionMode() == InRowMode || insertionMode() == TemplateContentsMode);
2555 #else
2556         ASSERT(insertionMode() != TemplateContentsMode);
2557         ASSERT(insertionMode() == InBodyMode || insertionMode() == InCellMode || insertionMode() == InCaptionMode || insertionMode() == InRowMode);
2558 #endif
2559         notImplemented(); // Emit parse error based on what elements are still open.
2560 #if ENABLE(TEMPLATE_ELEMENT)
2561         if (popAllTemplatesForEndOfFile()) {
2562             processEndOfFile(token);
2563             return;
2564         }
2565 #endif
2566         break;
2567     case AfterBodyMode:
2568     case AfterAfterBodyMode:
2569         ASSERT(insertionMode() == AfterBodyMode || insertionMode() == AfterAfterBodyMode);
2570         break;
2571     case InHeadNoscriptMode:
2572         ASSERT(insertionMode() == InHeadNoscriptMode);
2573         defaultForInHeadNoscript();
2574         processEndOfFile(token);
2575         return;
2576     case AfterFramesetMode:
2577     case AfterAfterFramesetMode:
2578         ASSERT(insertionMode() == AfterFramesetMode || insertionMode() == AfterAfterFramesetMode);
2579         break;
2580     case InColumnGroupMode:
2581         if (m_tree.currentIsRootNode()) {
2582             ASSERT(isParsingFragment());
2583             return; // FIXME: Should we break here instead of returning?
2584         }
2585 #if ENABLE(TEMPLATE_ELEMENT)
2586         ASSERT(m_tree.currentNode()->hasTagName(colgroupTag) || m_tree.currentNode()->hasTagName(templateTag));
2587 #else
2588         ASSERT(m_tree.currentNode()->hasTagName(colgroupTag));
2589 #endif
2590         processColgroupEndTagForInColumnGroup();
2591         // Fall through
2592     case InFramesetMode:
2593     case InTableMode:
2594     case InTableBodyMode:
2595     case InSelectInTableMode:
2596     case InSelectMode:
2597         ASSERT(insertionMode() == InSelectMode || insertionMode() == InSelectInTableMode || insertionMode() == InTableMode || insertionMode() == InFramesetMode || insertionMode() == InTableBodyMode || insertionMode() == InColumnGroupMode);
2598         if (m_tree.currentNode() != m_tree.openElements()->rootNode())
2599             parseError(token);
2600
2601 #if ENABLE(TEMPLATE_ELEMENT)
2602         if (popAllTemplatesForEndOfFile()) {
2603             processEndOfFile(token);
2604             return;
2605         }
2606 #endif
2607         break;
2608     case InTableTextMode:
2609         defaultForInTableText();
2610         processEndOfFile(token);
2611         return;
2612     case TextMode:
2613         parseError(token);
2614         if (m_tree.currentStackItem()->hasTagName(scriptTag))
2615             notImplemented(); // mark the script element as "already started".
2616         m_tree.openElements()->pop();
2617         ASSERT(m_originalInsertionMode != TextMode);
2618         setInsertionMode(m_originalInsertionMode);
2619         processEndOfFile(token);
2620         return;
2621     case TemplateContentsMode:
2622 #if ENABLE(TEMPLATE_ELEMENT)
2623         parseError(token);
2624         if (popAllTemplatesForEndOfFile()) {
2625             processEndOfFile(token);
2626             return;
2627         }
2628         break;
2629 #else
2630         ASSERT_NOT_REACHED();
2631 #endif
2632     }
2633     ASSERT(m_tree.currentNode());
2634     m_tree.openElements()->popAll();
2635 }
2636
2637 void HTMLTreeBuilder::defaultForInitial()
2638 {
2639     notImplemented();
2640     m_tree.setDefaultCompatibilityMode();
2641     // FIXME: parse error
2642     setInsertionMode(BeforeHTMLMode);
2643 }
2644
2645 void HTMLTreeBuilder::defaultForBeforeHTML()
2646 {
2647     AtomicHTMLToken startHTML(HTMLToken::StartTag, htmlTag.localName());
2648     m_tree.insertHTMLHtmlStartTagBeforeHTML(&startHTML);
2649     setInsertionMode(BeforeHeadMode);
2650 }
2651
2652 void HTMLTreeBuilder::defaultForBeforeHead()
2653 {
2654     AtomicHTMLToken startHead(HTMLToken::StartTag, headTag.localName());
2655     processStartTag(&startHead);
2656 }
2657
2658 void HTMLTreeBuilder::defaultForInHead()
2659 {
2660     AtomicHTMLToken endHead(HTMLToken::EndTag, headTag.localName());
2661     processEndTag(&endHead);
2662 }
2663
2664 void HTMLTreeBuilder::defaultForInHeadNoscript()
2665 {
2666     AtomicHTMLToken endNoscript(HTMLToken::EndTag, noscriptTag.localName());
2667     processEndTag(&endNoscript);
2668 }
2669
2670 void HTMLTreeBuilder::defaultForAfterHead()
2671 {
2672     AtomicHTMLToken startBody(HTMLToken::StartTag, bodyTag.localName());
2673     processStartTag(&startBody);
2674     m_framesetOk = true;
2675 }
2676
2677 void HTMLTreeBuilder::defaultForInTableText()
2678 {
2679     String characters = m_pendingTableCharacters.toString();
2680     m_pendingTableCharacters.clear();
2681     if (!isAllWhitespace(characters)) {
2682         // FIXME: parse error
2683         HTMLConstructionSite::RedirectToFosterParentGuard redirecter(m_tree);
2684         m_tree.reconstructTheActiveFormattingElements();
2685         m_tree.insertTextNode(characters, NotAllWhitespace);
2686         m_framesetOk = false;
2687         setInsertionMode(m_originalInsertionMode);
2688         return;
2689     }
2690     m_tree.insertTextNode(characters);
2691     setInsertionMode(m_originalInsertionMode);
2692 }
2693
2694 bool HTMLTreeBuilder::processStartTagForInHead(AtomicHTMLToken* token)
2695 {
2696     ASSERT(token->type() == HTMLToken::StartTag);
2697     if (token->name() == htmlTag) {
2698         processHtmlStartTagForInBody(token);
2699         return true;
2700     }
2701     if (token->name() == baseTag
2702         || token->name() == basefontTag
2703         || token->name() == bgsoundTag
2704         || token->name() == commandTag
2705         || token->name() == linkTag
2706         || token->name() == metaTag) {
2707         m_tree.insertSelfClosingHTMLElement(token);
2708         // Note: The custom processing for the <meta> tag is done in HTMLMetaElement::process().
2709         return true;
2710     }
2711     if (token->name() == titleTag) {
2712         processGenericRCDATAStartTag(token);
2713         return true;
2714     }
2715     if (token->name() == noscriptTag) {
2716         if (m_options.scriptEnabled) {
2717             processGenericRawTextStartTag(token);
2718             return true;
2719         }
2720         m_tree.insertHTMLElement(token);
2721         setInsertionMode(InHeadNoscriptMode);
2722         return true;
2723     }
2724     if (token->name() == noframesTag || token->name() == styleTag) {
2725         processGenericRawTextStartTag(token);
2726         return true;
2727     }
2728     if (token->name() == scriptTag) {
2729         processScriptStartTag(token);
2730         if (m_options.usePreHTML5ParserQuirks && token->selfClosing())
2731             processFakeEndTag(scriptTag);
2732         return true;
2733     }
2734 #if ENABLE(TEMPLATE_ELEMENT)
2735     if (token->name() == templateTag) {
2736         processTemplateStartTag(token);
2737         return true;
2738     }
2739 #endif
2740     if (token->name() == headTag) {
2741         parseError(token);
2742         return true;
2743     }
2744     return false;
2745 }
2746
2747 void HTMLTreeBuilder::processGenericRCDATAStartTag(AtomicHTMLToken* token)
2748 {
2749     ASSERT(token->type() == HTMLToken::StartTag);
2750     m_tree.insertHTMLElement(token);
2751     if (m_parser->tokenizer())
2752         m_parser->tokenizer()->setState(HTMLTokenizer::RCDATAState);
2753     m_originalInsertionMode = m_insertionMode;
2754     setInsertionMode(TextMode);
2755 }
2756
2757 void HTMLTreeBuilder::processGenericRawTextStartTag(AtomicHTMLToken* token)
2758 {
2759     ASSERT(token->type() == HTMLToken::StartTag);
2760     m_tree.insertHTMLElement(token);
2761     if (m_parser->tokenizer())
2762         m_parser->tokenizer()->setState(HTMLTokenizer::RAWTEXTState);
2763     m_originalInsertionMode = m_insertionMode;
2764     setInsertionMode(TextMode);
2765 }
2766
2767 void HTMLTreeBuilder::processScriptStartTag(AtomicHTMLToken* token)
2768 {
2769     ASSERT(token->type() == HTMLToken::StartTag);
2770     m_tree.insertScriptElement(token);
2771     if (m_parser->tokenizer())
2772         m_parser->tokenizer()->setState(HTMLTokenizer::ScriptDataState);
2773     m_originalInsertionMode = m_insertionMode;
2774
2775     TextPosition position = m_parser->textPosition();
2776
2777     m_scriptToProcessStartPosition = position;
2778
2779     setInsertionMode(TextMode);
2780 }
2781
2782 // http://www.whatwg.org/specs/web-apps/current-work/multipage/tree-construction.html#tree-construction
2783 bool HTMLTreeBuilder::shouldProcessTokenInForeignContent(AtomicHTMLToken* token)
2784 {
2785     if (m_tree.isEmpty())
2786         return false;
2787     HTMLStackItem* item = m_tree.currentStackItem();
2788     if (item->isInHTMLNamespace())
2789         return false;
2790     if (HTMLElementStack::isMathMLTextIntegrationPoint(item)) {
2791         if (token->type() == HTMLToken::StartTag
2792             && token->name() != MathMLNames::mglyphTag
2793             && token->name() != MathMLNames::malignmarkTag)
2794             return false;
2795         if (token->type() == HTMLToken::Character)
2796             return false;
2797     }
2798     if (item->hasTagName(MathMLNames::annotation_xmlTag)
2799         && token->type() == HTMLToken::StartTag
2800         && token->name() == SVGNames::svgTag)
2801         return false;
2802     if (HTMLElementStack::isHTMLIntegrationPoint(item)) {
2803         if (token->type() == HTMLToken::StartTag)
2804             return false;
2805         if (token->type() == HTMLToken::Character)
2806             return false;
2807     }
2808     if (token->type() == HTMLToken::EndOfFile)
2809         return false;
2810     return true;
2811 }
2812
2813 void HTMLTreeBuilder::processTokenInForeignContent(AtomicHTMLToken* token)
2814 {
2815     switch (token->type()) {
2816     case HTMLToken::Uninitialized:
2817         ASSERT_NOT_REACHED();
2818         break;
2819     case HTMLToken::DOCTYPE:
2820         parseError(token);
2821         break;
2822     case HTMLToken::StartTag: {
2823         if (token->name() == bTag
2824             || token->name() == bigTag
2825             || token->name() == blockquoteTag
2826             || token->name() == bodyTag
2827             || token->name() == brTag
2828             || token->name() == centerTag
2829             || token->name() == codeTag
2830             || token->name() == ddTag
2831             || token->name() == divTag
2832             || token->name() == dlTag
2833             || token->name() == dtTag
2834             || token->name() == emTag
2835             || token->name() == embedTag
2836             || isNumberedHeaderTag(token->name())
2837             || token->name() == headTag
2838             || token->name() == hrTag
2839             || token->name() == iTag
2840             || token->name() == imgTag
2841             || token->name() == liTag
2842             || token->name() == listingTag
2843             || token->name() == menuTag
2844             || token->name() == metaTag
2845             || token->name() == nobrTag
2846             || token->name() == olTag
2847             || token->name() == pTag
2848             || token->name() == preTag
2849             || token->name() == rubyTag
2850             || token->name() == sTag
2851             || token->name() == smallTag
2852             || token->name() == spanTag
2853             || token->name() == strongTag
2854             || token->name() == strikeTag
2855             || token->name() == subTag
2856             || token->name() == supTag
2857             || token->name() == tableTag
2858             || token->name() == ttTag
2859             || token->name() == uTag
2860             || token->name() == ulTag
2861             || token->name() == varTag
2862             || (token->name() == fontTag && (token->getAttributeItem(colorAttr) || token->getAttributeItem(faceAttr) || token->getAttributeItem(sizeAttr)))) {
2863             parseError(token);
2864             m_tree.openElements()->popUntilForeignContentScopeMarker();
2865             processStartTag(token);
2866             return;
2867         }
2868         const AtomicString& currentNamespace = m_tree.currentStackItem()->namespaceURI();
2869         if (currentNamespace == MathMLNames::mathmlNamespaceURI)
2870             adjustMathMLAttributes(token);
2871         if (currentNamespace == SVGNames::svgNamespaceURI) {
2872             adjustSVGTagNameCase(token);
2873             adjustSVGAttributes(token);
2874         }
2875         adjustForeignAttributes(token);
2876         m_tree.insertForeignElement(token, currentNamespace);
2877         break;
2878     }
2879     case HTMLToken::EndTag: {
2880         if (m_tree.currentStackItem()->namespaceURI() == SVGNames::svgNamespaceURI)
2881             adjustSVGTagNameCase(token);
2882
2883         if (token->name() == SVGNames::scriptTag && m_tree.currentStackItem()->hasTagName(SVGNames::scriptTag)) {
2884             m_scriptToProcess = m_tree.currentElement();
2885             m_tree.openElements()->pop();
2886             return;
2887         }
2888         if (!m_tree.currentStackItem()->isInHTMLNamespace()) {
2889             // FIXME: This code just wants an Element* iterator, instead of an ElementRecord*
2890             HTMLElementStack::ElementRecord* nodeRecord = m_tree.openElements()->topRecord();
2891             if (!nodeRecord->stackItem()->hasLocalName(token->name()))
2892                 parseError(token);
2893             while (1) {
2894                 if (nodeRecord->stackItem()->hasLocalName(token->name())) {
2895                     m_tree.openElements()->popUntilPopped(nodeRecord->element());
2896                     return;
2897                 }
2898                 nodeRecord = nodeRecord->next();
2899
2900                 if (nodeRecord->stackItem()->isInHTMLNamespace())
2901                     break;
2902             }
2903         }
2904         // Otherwise, process the token according to the rules given in the section corresponding to the current insertion mode in HTML content.
2905         processEndTag(token);
2906         break;
2907     }
2908     case HTMLToken::Comment:
2909         m_tree.insertComment(token);
2910         return;
2911     case HTMLToken::Character: {
2912         String characters = String(token->characters(), token->charactersLength());
2913         m_tree.insertTextNode(characters);
2914         if (m_framesetOk && !isAllWhitespaceOrReplacementCharacters(characters))
2915             m_framesetOk = false;
2916         break;
2917     }
2918     case HTMLToken::EndOfFile:
2919         ASSERT_NOT_REACHED();
2920         break;
2921     }
2922 }
2923
2924 void HTMLTreeBuilder::finished()
2925 {
2926     if (isParsingFragment())
2927         return;
2928
2929 #if ENABLE(TEMPLATE_ELEMENT)
2930     ASSERT(m_templateInsertionModes.isEmpty());
2931 #endif
2932
2933     ASSERT(m_isAttached);
2934     // Warning, this may detach the parser. Do not do anything else after this.
2935     m_tree.finishedParsing();
2936 }
2937
2938 void HTMLTreeBuilder::parseError(AtomicHTMLToken*)
2939 {
2940 }
2941
2942 }