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