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