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