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