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