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