2010-07-02 Adam Barth <abarth@webkit.org>
[WebKit-https.git] / WebCore / html / HTMLTreeBuilder.cpp
1 /*
2  * Copyright (C) 2010 Google, Inc. All Rights Reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY GOOGLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL GOOGLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "HTMLTreeBuilder.h"
28
29 #include "Comment.h"
30 #include "DocumentFragment.h"
31 #include "DocumentType.h"
32 #include "Element.h"
33 #include "Frame.h"
34 #include "HTMLElementFactory.h"
35 #include "HTMLScriptElement.h"
36 #include "HTMLTokenizer.h"
37 #include "HTMLToken.h"
38 #include "HTMLDocument.h"
39 #include "HTMLHtmlElement.h"
40 #include "LegacyHTMLDocumentParser.h"
41 #include "HTMLNames.h"
42 #include "LegacyHTMLTreeBuilder.h"
43 #include "NotImplemented.h"
44 #include "Settings.h"
45 #include "ScriptController.h"
46 #include "Text.h"
47 #include <wtf/UnusedParam.h>
48
49 namespace WebCore {
50
51 using namespace HTMLNames;
52
53 static const int uninitializedLineNumberValue = -1;
54
55 namespace {
56
57 inline bool isTreeBuilderWhiteSpace(UChar cc)
58 {
59     return cc == '\t' || cc == '\x0A' || cc == '\x0C' || cc == '\x0D' || cc == ' ';
60 }
61
62 bool shouldUseLegacyTreeBuilder(Document* document)
63 {
64     return !document->settings() || !document->settings()->html5TreeBuilderEnabled();
65 }
66
67 } // namespace
68
69 HTMLTreeBuilder::HTMLTreeBuilder(HTMLTokenizer* tokenizer, HTMLDocument* document, bool reportErrors)
70     : m_framesetOk(true)
71     , m_document(document)
72     , m_reportErrors(reportErrors)
73     , m_isPaused(false)
74     , m_insertionMode(InitialMode)
75     , m_originalInsertionMode(InitialMode)
76     , m_tokenizer(tokenizer)
77     , m_legacyTreeBuilder(shouldUseLegacyTreeBuilder(document) ? new LegacyHTMLTreeBuilder(document, reportErrors) : 0)
78     , m_lastScriptElementStartLine(uninitializedLineNumberValue)
79     , m_scriptToProcessStartLine(uninitializedLineNumberValue)
80     , m_fragmentScriptingPermission(FragmentScriptingAllowed)
81     , m_isParsingFragment(false)
82 {
83 }
84
85 // FIXME: Member variables should be grouped into self-initializing structs to
86 // minimize code duplication between these constructors.
87 HTMLTreeBuilder::HTMLTreeBuilder(HTMLTokenizer* tokenizer, DocumentFragment* fragment, FragmentScriptingPermission scriptingPermission)
88     : m_framesetOk(true)
89     , m_document(fragment->document())
90     , m_reportErrors(false) // FIXME: Why not report errors in fragments?
91     , m_isPaused(false)
92     , m_insertionMode(InitialMode)
93     , m_originalInsertionMode(InitialMode)
94     , m_tokenizer(tokenizer)
95     , m_legacyTreeBuilder(new LegacyHTMLTreeBuilder(fragment, scriptingPermission))
96     , m_lastScriptElementStartLine(uninitializedLineNumberValue)
97     , m_scriptToProcessStartLine(uninitializedLineNumberValue)
98     , m_fragmentScriptingPermission(scriptingPermission)
99     , m_isParsingFragment(true)
100 {
101 }
102
103 HTMLTreeBuilder::~HTMLTreeBuilder()
104 {
105 }
106
107 static void convertToOldStyle(const AtomicHTMLToken& token, Token& oldStyleToken)
108 {
109     switch (token.type()) {
110     case HTMLToken::Uninitialized:
111     case HTMLToken::DOCTYPE:
112         ASSERT_NOT_REACHED();
113         break;
114     case HTMLToken::EndOfFile:
115         ASSERT_NOT_REACHED();
116         notImplemented();
117         break;
118     case HTMLToken::StartTag:
119     case HTMLToken::EndTag: {
120         oldStyleToken.beginTag = (token.type() == HTMLToken::StartTag);
121         oldStyleToken.selfClosingTag = token.selfClosing();
122         oldStyleToken.tagName = token.name();
123         oldStyleToken.attrs = token.attributes();
124         break;
125     }
126     case HTMLToken::Comment:
127         oldStyleToken.tagName = commentAtom;
128         oldStyleToken.text = token.comment().impl();
129         break;
130     case HTMLToken::Character:
131         oldStyleToken.tagName = textAtom;
132         oldStyleToken.text = token.characters().impl();
133         break;
134     }
135 }
136
137 void HTMLTreeBuilder::handleScriptStartTag()
138 {
139     notImplemented(); // The HTML frgment case?
140     m_tokenizer->setState(HTMLTokenizer::ScriptDataState);
141     notImplemented(); // Save insertion mode.
142 }
143
144 void HTMLTreeBuilder::handleScriptEndTag(Element* scriptElement, int scriptStartLine)
145 {
146     ASSERT(!m_scriptToProcess); // Caller never called takeScriptToProcess!
147     ASSERT(m_scriptToProcessStartLine == uninitializedLineNumberValue); // Caller never called takeScriptToProcess!
148     notImplemented(); // Save insertion mode and insertion point?
149
150     // Pause ourselves so that parsing stops until the script can be processed by the caller.
151     m_isPaused = true;
152     m_scriptToProcess = scriptElement;
153     // Lexer line numbers are 0-based, ScriptSourceCode expects 1-based lines,
154     // so we convert here before passing the line number off to HTMLScriptRunner.
155     m_scriptToProcessStartLine = scriptStartLine + 1;
156 }
157
158 PassRefPtr<Element> HTMLTreeBuilder::takeScriptToProcess(int& scriptStartLine)
159 {
160     // Unpause ourselves, callers may pause us again when processing the script.
161     // The HTML5 spec is written as though scripts are executed inside the tree
162     // builder.  We pause the parser to exit the tree builder, and then resume
163     // before running scripts.
164     m_isPaused = false;
165     scriptStartLine = m_scriptToProcessStartLine;
166     m_scriptToProcessStartLine = uninitializedLineNumberValue;
167     return m_scriptToProcess.release();
168 }
169
170 HTMLTokenizer::State HTMLTreeBuilder::adjustedLexerState(HTMLTokenizer::State state, const AtomicString& tagName, Frame* frame)
171 {
172     if (tagName == textareaTag || tagName == titleTag)
173         return HTMLTokenizer::RCDATAState;
174
175     if (tagName == styleTag || tagName == iframeTag || tagName == xmpTag || tagName == noembedTag
176         || tagName == noframesTag || (tagName == noscriptTag && isScriptingFlagEnabled(frame)))
177         return HTMLTokenizer::RAWTEXTState;
178
179     if (tagName == plaintextTag)
180         return HTMLTokenizer::PLAINTEXTState;
181
182     return state;
183 }
184
185 void HTMLTreeBuilder::passTokenToLegacyParser(HTMLToken& token)
186 {
187     if (token.type() == HTMLToken::DOCTYPE) {
188         DoctypeToken doctypeToken;
189         doctypeToken.m_name.append(token.name().data(), token.name().size());
190         doctypeToken.m_publicID = token.publicIdentifier();
191         doctypeToken.m_systemID = token.systemIdentifier();
192         doctypeToken.m_forceQuirks = token.forceQuirks();
193
194         m_legacyTreeBuilder->parseDoctypeToken(&doctypeToken);
195         return;
196     }
197
198     if (token.type() == HTMLToken::EndOfFile)
199         return;
200
201     // For now, we translate into an old-style token for testing.
202     Token oldStyleToken;
203     AtomicHTMLToken atomicToken(token);
204     convertToOldStyle(atomicToken, oldStyleToken);
205
206     RefPtr<Node> result =  m_legacyTreeBuilder->parseToken(&oldStyleToken);
207     if (token.type() == HTMLToken::StartTag) {
208         // This work is supposed to be done by the parser, but
209         // when using the old parser for we have to do this manually.
210         if (oldStyleToken.tagName == scriptTag) {
211             handleScriptStartTag();
212             m_lastScriptElement = static_pointer_cast<Element>(result);
213             m_lastScriptElementStartLine = m_tokenizer->lineNumber();
214         } else if (oldStyleToken.tagName == preTag || oldStyleToken.tagName == listingTag)
215             m_tokenizer->skipLeadingNewLineForListing();
216         else
217             m_tokenizer->setState(adjustedLexerState(m_tokenizer->state(), oldStyleToken.tagName, m_document->frame()));
218     } else if (token.type() == HTMLToken::EndTag) {
219         if (oldStyleToken.tagName == scriptTag) {
220             if (m_lastScriptElement) {
221                 ASSERT(m_lastScriptElementStartLine != uninitializedLineNumberValue);
222                 if (m_fragmentScriptingPermission == FragmentScriptingNotAllowed) {
223                     // FIXME: This is a horrible hack for platform/Pasteboard.
224                     // Clear the <script> tag when using the Parser to create
225                     // a DocumentFragment for pasting so that javascript content
226                     // does not show up in pasted HTML.
227                     m_lastScriptElement->removeChildren();
228                 } else if (insertionMode() != AfterFramesetMode)
229                     handleScriptEndTag(m_lastScriptElement.get(), m_lastScriptElementStartLine);
230                 m_lastScriptElement = 0;
231                 m_lastScriptElementStartLine = uninitializedLineNumberValue;
232             }
233         } else if (oldStyleToken.tagName == framesetTag)
234             setInsertionMode(AfterFramesetMode);
235     }
236 }
237
238 void HTMLTreeBuilder::constructTreeFromToken(HTMLToken& rawToken)
239 {
240     if (m_legacyTreeBuilder) {
241         passTokenToLegacyParser(rawToken);
242         return;
243     }
244
245     AtomicHTMLToken token(rawToken);
246     processToken(token);
247 }
248
249 void HTMLTreeBuilder::processToken(AtomicHTMLToken& token)
250 {
251     switch (token.type()) {
252     case HTMLToken::Uninitialized:
253         ASSERT_NOT_REACHED();
254         break;
255     case HTMLToken::DOCTYPE:
256         processDoctypeToken(token);
257         break;
258     case HTMLToken::StartTag:
259         processStartTag(token);
260         break;
261     case HTMLToken::EndTag:
262         processEndTag(token);
263         break;
264     case HTMLToken::Comment:
265         processComment(token);
266         return;
267     case HTMLToken::Character:
268         processCharacter(token);
269         break;
270     case HTMLToken::EndOfFile:
271         processEndOfFile(token);
272         break;
273     }
274 }
275
276 void HTMLTreeBuilder::processDoctypeToken(AtomicHTMLToken& token)
277 {
278     if (insertionMode() == InitialMode) {
279         insertDoctype(token);
280         return;
281     }
282     parseError(token);
283 }
284
285 void HTMLTreeBuilder::insertHTMLStartTagBeforeHTML(AtomicHTMLToken& token)
286 {
287     RefPtr<Element> element = HTMLHtmlElement::create(m_document);
288     element->setAttributeMap(token.attributes(), m_fragmentScriptingPermission);
289     m_openElements.pushHTMLHtmlElement(attach(m_document, element.release()));
290 }
291
292 void HTMLTreeBuilder::mergeAttributesFromTokenIntoElement(AtomicHTMLToken& token, Element* element)
293 {
294     if (!token.attributes())
295         return;
296
297     NamedNodeMap* attributes = element->attributes(false);
298     for (unsigned i = 0; i < token.attributes()->length(); ++i) {
299         Attribute* attribute = token.attributes()->attributeItem(i);
300         if (!attributes->getAttributeItem(attribute->name()))
301             element->setAttribute(attribute->name(), attribute->value());
302     }
303 }
304
305 void HTMLTreeBuilder::insertHTMLStartTagInBody(AtomicHTMLToken& token)
306 {
307     parseError(token);
308     mergeAttributesFromTokenIntoElement(token, m_openElements.htmlElement());
309 }
310
311 void HTMLTreeBuilder::processStartTag(AtomicHTMLToken& token)
312 {
313     switch (insertionMode()) {
314     case InitialMode:
315         ASSERT(insertionMode() == InitialMode);
316         processDefaultForInitialMode(token);
317         // Fall through.
318     case BeforeHTMLMode:
319         ASSERT(insertionMode() == BeforeHTMLMode);
320         if (token.name() == htmlTag) {
321             insertHTMLStartTagBeforeHTML(token);
322             setInsertionMode(BeforeHeadMode);
323             return;
324         }
325         processDefaultForBeforeHTMLMode(token);
326         // Fall through.
327     case BeforeHeadMode:
328         ASSERT(insertionMode() == BeforeHeadMode);
329         if (token.name() == htmlTag) {
330             insertHTMLStartTagInBody(token);
331             return;
332         }
333         if (token.name() == headTag) {
334             insertHTMLHeadElement(token);
335             setInsertionMode(InHeadMode);
336             return;
337         }
338         processDefaultForBeforeHeadMode(token);
339         // Fall through.
340     case InHeadMode:
341         ASSERT(insertionMode() == InHeadMode);
342         if (processStartTagForInHead(token))
343             return;
344         processDefaultForInHeadMode(token);
345         // Fall through.
346     case AfterHeadMode:
347         ASSERT(insertionMode() == AfterHeadMode);
348         if (token.name() == htmlTag) {
349             insertHTMLStartTagInBody(token);
350             return;
351         }
352         if (token.name() == bodyTag) {
353             m_framesetOk = false;
354             insertHTMLBodyElement(token);
355             m_insertionMode = InBodyMode;
356             return;
357         }
358         if (token.name() == framesetTag) {
359             insertElement(token);
360             setInsertionMode(InFramesetMode);
361             return;
362         }
363         if (token.name() == baseTag || token.name() == linkTag || token.name() == metaTag || token.name() == noframesTag || token.name() == scriptTag || token.name() == styleTag || token.name() == titleTag) {
364             parseError(token);
365             ASSERT(m_headElement);
366             m_openElements.pushHTMLHeadElement(m_headElement);
367             processStartTagForInHead(token);
368             m_openElements.removeHTMLHeadElement(m_headElement.get());
369             return;
370         }
371         if (token.name() == headTag) {
372             parseError(token);
373             return;
374         }
375         processDefaultForAfterHeadMode(token);
376         // Fall through
377     case InBodyMode:
378         ASSERT(insertionMode() == InBodyMode);
379         if (token.name() == htmlTag) {
380             insertHTMLStartTagInBody(token);
381             return;
382         }
383         if (token.name() == baseTag || token.name() == "command" || token.name() == linkTag || token.name() == metaTag || token.name() == noframesTag || token.name() == scriptTag || token.name() == styleTag || token.name() == titleTag) {
384             bool didProcess = processStartTagForInHead(token);
385             ASSERT_UNUSED(didProcess, didProcess);
386             return;
387         }
388         if (token.name() == bodyTag) {
389             parseError(token);
390             notImplemented(); // fragment case
391             mergeAttributesFromTokenIntoElement(token, m_openElements.bodyElement());
392             return;
393         }
394         if (token.name() == framesetTag) {
395             notImplemented();
396             return;
397         }
398         if (token.name() == addressTag || token.name() == articleTag || token.name() == asideTag || token.name() == blockquoteTag || token.name() == centerTag || token.name() == "details" || token.name() == dirTag || token.name() == divTag || token.name() == dlTag || token.name() == fieldsetTag || token.name() == "figure" || token.name() == footerTag || token.name() == headerTag || token.name() == hgroupTag || token.name() == menuTag || token.name() == navTag || token.name() == olTag || token.name() == pTag || token.name() == sectionTag || token.name() == ulTag) {
399             notImplemented();
400             insertElement(token);
401             return;
402         }
403         if (token.name() == h1Tag || token.name() == h2Tag || token.name() == h3Tag || token.name() == h4Tag || token.name() == h5Tag || token.name() == h6Tag) {
404             notImplemented();
405             insertElement(token);
406             return;
407         }
408         if (token.name() == preTag || token.name() == listingTag) {
409             notImplemented();
410             insertElement(token);
411             m_tokenizer->skipLeadingNewLineForListing();
412             m_framesetOk = false;
413             return;
414         }
415         if (token.name() == formTag) {
416             notImplemented();
417             insertElement(token);
418             m_formElement = currentElement();
419             return;
420         }
421         if (token.name() == liTag) {
422             notImplemented();
423             insertElement(token);
424             return;
425         }
426         if (token.name() == ddTag || token.name() == dtTag) {
427             notImplemented();
428             insertElement(token);
429             return;
430         }
431         if (token.name() == plaintextTag) {
432             notImplemented();
433             insertElement(token);
434             m_tokenizer->setState(HTMLTokenizer::PLAINTEXTState);
435             return;
436         }
437         if (token.name() == buttonTag) {
438             notImplemented();
439             reconstructTheActiveFormattingElements();
440             insertElement(token);
441             m_framesetOk = false;
442             return;
443         }
444         if (token.name() == aTag) {
445             notImplemented();
446             reconstructTheActiveFormattingElements();
447             insertFormattingElement(token);
448             return;
449         }
450         if (token.name() == bTag || token.name() == bigTag || token.name() == codeTag || token.name() == emTag || token.name() == fontTag || token.name() == iTag || token.name() == sTag || token.name() == smallTag || token.name() == strikeTag || token.name() == strongTag || token.name() == ttTag || token.name() == uTag) {
451             reconstructTheActiveFormattingElements();
452             insertFormattingElement(token);
453             return;
454         }
455         if (token.name() == nobrTag) {
456             reconstructTheActiveFormattingElements();
457             notImplemented();
458             insertFormattingElement(token);
459             return;
460         }
461         if (token.name() == appletTag || token.name() == marqueeTag || token.name() == objectTag) {
462             reconstructTheActiveFormattingElements();
463             insertElement(token);
464             notImplemented();
465             m_framesetOk = false;
466             return;
467         }
468         if (token.name() == tableTag) {
469             notImplemented();
470             insertElement(token);
471             m_framesetOk = false;
472             m_insertionMode = InTableMode;
473             return;
474         }
475         if (token.name() == areaTag || token.name() == basefontTag || token.name() == "bgsound" || token.name() == brTag || token.name() == embedTag || token.name() == imgTag || token.name() == inputTag || token.name() == keygenTag || token.name() == wbrTag) {
476             reconstructTheActiveFormattingElements();
477             insertSelfClosingElement(token);
478             m_framesetOk = false;
479             return;
480         }
481         if (token.name() == paramTag || token.name() == sourceTag || token.name() == "track") {
482             insertSelfClosingElement(token);
483             return;
484         }
485         if (token.name() == hrTag) {
486             notImplemented();
487             insertSelfClosingElement(token);
488             m_framesetOk = false;
489             return;
490         }
491         if (token.name() == imageTag) {
492             parseError(token);
493             notImplemented();
494             // Apparently we're not supposed to ask.
495             return;
496         }
497         if (token.name() == isindexTag) {
498             parseError(token);
499             notImplemented();
500             return;
501         }
502         if (token.name() == textareaTag) {
503             insertElement(token);
504             m_tokenizer->skipLeadingNewLineForListing();
505             m_tokenizer->setState(HTMLTokenizer::RCDATAState);
506             m_originalInsertionMode = m_insertionMode;
507             m_framesetOk = false;
508             m_insertionMode = TextMode;
509             return;
510         }
511         if (token.name() == xmpTag) {
512             notImplemented();
513             reconstructTheActiveFormattingElements();
514             m_framesetOk = false;
515             insertGenericRawTextElement(token);
516             return;
517         }
518         if (token.name() == iframeTag) {
519             m_framesetOk = false;
520             insertGenericRawTextElement(token);
521             return;
522         }
523         if (token.name() == noembedTag) {
524             insertGenericRawTextElement(token);
525             return;
526         }
527         if (token.name() == noscriptTag && isScriptingFlagEnabled(m_document->frame())) {
528             insertGenericRawTextElement(token);
529             return;
530         }
531         if (token.name() == selectTag) {
532             reconstructTheActiveFormattingElements();
533             insertElement(token);
534             m_framesetOk = false;
535             if (m_insertionMode == InTableMode || m_insertionMode == InCaptionMode || m_insertionMode == InColumnGroupMode || m_insertionMode == InTableBodyMode || m_insertionMode == InRowMode || m_insertionMode == InCellMode)
536                 m_insertionMode = InSelectInTableMode;
537             else
538                 m_insertionMode = InSelectMode;
539             return;
540         }
541         if (token.name() == optgroupTag || token.name() == optionTag) {
542             notImplemented();
543             reconstructTheActiveFormattingElements();
544             insertElement(token);
545             return;
546         }
547         if (token.name() == rpTag || token.name() == rtTag) {
548             notImplemented();
549             insertElement(token);
550             return;
551         }
552         if (token.name() == "math") {
553             // This is the MathML foreign content branch point.
554             notImplemented();
555         }
556         if (token.name() == "svg") {
557             // This is the SVG foreign content branch point.
558             notImplemented();
559         }
560         if (token.name() == captionTag || token.name() == colTag || token.name() == colgroupTag || token.name() == frameTag || token.name() == headTag || token.name() == tbodyTag || token.name() == tdTag || token.name() == tfootTag || token.name() == thTag || token.name() == theadTag || token.name() == trTag) {
561             parseError(token);
562             return;
563         }
564         reconstructTheActiveFormattingElements();
565         insertElement(token);
566         break;
567     case AfterBodyMode:
568         ASSERT(insertionMode() == AfterBodyMode);
569         if (token.name() == htmlTag) {
570             insertHTMLStartTagInBody(token);
571             return;
572         }
573         m_insertionMode = InBodyMode;
574         processStartTag(token);
575         break;
576     case InHeadNoscriptMode:
577         ASSERT(insertionMode() == InHeadNoscriptMode);
578         if (token.name() == htmlTag) {
579             insertHTMLStartTagInBody(token);
580             return;
581         }
582         if (token.name() == linkTag || token.name() == metaTag || token.name() == noframesTag || token.name() == styleTag) {
583             bool didProcess = processStartTagForInHead(token);
584             ASSERT_UNUSED(didProcess, didProcess);
585             return;
586         }
587         if (token.name() == htmlTag || token.name() == noscriptTag) {
588             parseError(token);
589             return;
590         }
591         processDefaultForInHeadNoscriptMode(token);
592         processToken(token);
593         break;
594     default:
595         notImplemented();
596     }
597 }
598
599 bool HTMLTreeBuilder::processBodyEndTagForInBody(AtomicHTMLToken& token)
600 {
601     if (!m_openElements.inScope(bodyTag.localName())) {
602         parseError(token);
603         return false;
604     }
605     notImplemented();
606     m_insertionMode = AfterBodyMode;
607     return true;
608 }
609
610 void HTMLTreeBuilder::processEndTag(AtomicHTMLToken& token)
611 {
612     switch (insertionMode()) {
613     case InitialMode:
614         ASSERT(insertionMode() == InitialMode);
615         processDefaultForInitialMode(token);
616         // Fall through.
617     case BeforeHTMLMode:
618         ASSERT(insertionMode() == BeforeHTMLMode);
619         if (token.name() != headTag && token.name() != bodyTag && token.name() != htmlTag && token.name() != brTag) {
620             parseError(token);
621             return;
622         }
623         processDefaultForBeforeHTMLMode(token);
624         // Fall through.
625     case BeforeHeadMode:
626         ASSERT(insertionMode() == BeforeHeadMode);
627         if (token.name() != headTag && token.name() != bodyTag && token.name() != brTag) {
628             parseError(token);
629             return;
630         }
631         processDefaultForBeforeHeadMode(token);
632         // Fall through.
633     case InHeadMode:
634         ASSERT(insertionMode() == InHeadMode);
635         if (token.name() == headTag) {
636             m_openElements.popHTMLHeadElement();
637             setInsertionMode(AfterHeadMode);
638             return;
639         }
640         if (token.name() != bodyTag && token.name() != htmlTag && token.name() != brTag) {
641             parseError(token);
642             return;
643         }
644         processDefaultForInHeadMode(token);
645         // Fall through.
646     case AfterHeadMode:
647         ASSERT(insertionMode() == AfterHeadMode);
648         if (token.name() != bodyTag && token.name() != htmlTag && token.name() != brTag) {
649             parseError(token);
650             return;
651         }
652         processDefaultForAfterHeadMode(token);
653         // Fall through
654     case InBodyMode:
655         ASSERT(insertionMode() == InBodyMode);
656         if (token.name() == bodyTag) {
657             processBodyEndTagForInBody(token);
658             return;
659         }
660         if (token.name() == htmlTag) {
661             if (processBodyEndTagForInBody(token))
662                 notImplemented(); // Re-process the curent token.
663             return;
664         }
665         if (token.name() == addressTag || token.name() == articleTag || token.name() == asideTag || token.name() == blockquoteTag || token.name() == buttonTag || token.name() == centerTag || token.name() == "details" || token.name() == dirTag || token.name() == divTag || token.name() == dlTag || token.name() == fieldsetTag || token.name() == "figure" || token.name() == footerTag || token.name() == headerTag || token.name() == hgroupTag || token.name() == listingTag || token.name() == menuTag || token.name() == navTag || token.name() == olTag || token.name() == preTag || token.name() == sectionTag || token.name() == ulTag) {
666             if (!m_openElements.inScope(token.name())) {
667                 parseError(token);
668                 return;
669             }
670             generateImpliedEndTags();
671             if (currentElement()->tagQName() != token.name())
672                 parseError(token);
673             m_openElements.popUntil(token.name());
674             m_openElements.pop();
675         }
676         if (token.name() == formTag) {
677             RefPtr<Element> node = m_formElement.release();
678             if (!node || !m_openElements.inScope(node.get())) {
679                 parseError(token);
680                 return;
681             }
682             generateImpliedEndTags();
683             if (currentElement() != node.get())
684                 parseError(token);
685             m_openElements.remove(node.get());
686         }
687         if (token.name() == pTag) {
688             if (!m_openElements.inScope(token.name())) {
689                 parseError(token);
690                 notImplemented();
691                 return;
692             }
693             generateImpliedEndTagsWithExclusion(token.name());
694             if (!currentElement()->hasLocalName(token.name()))
695                 parseError(token);
696             m_openElements.popUntil(token.name());
697             m_openElements.pop();
698             return;
699         }
700         if (token.name() == liTag) {
701             if (!m_openElements.inListItemScope(token.name())) {
702                 parseError(token);
703                 return;
704             }
705             generateImpliedEndTagsWithExclusion(token.name());
706             if (!currentElement()->hasLocalName(token.name()))
707                 parseError(token);
708             m_openElements.popUntil(token.name());
709             m_openElements.pop();
710             return;
711         }
712         if (token.name() == ddTag || token.name() == dtTag) {
713             if (!m_openElements.inScope(token.name())) {
714                 parseError(token);
715                 return;
716             }
717             generateImpliedEndTagsWithExclusion(token.name());
718             if (!currentElement()->hasLocalName(token.name()))
719                 parseError(token);
720             m_openElements.popUntil(token.name());
721             m_openElements.pop();
722             return;
723         }
724         if (token.name() == h1Tag || token.name() == h2Tag || token.name() == h3Tag || token.name() == h4Tag || token.name() == h5Tag || token.name() == h6Tag) {
725             if (!m_openElements.inScope(token.name())) {
726                 parseError(token);
727                 return;
728             }
729             generateImpliedEndTags();
730             if (!currentElement()->hasLocalName(token.name()))
731                 parseError(token);
732             m_openElements.popUntil(token.name());
733             m_openElements.pop();
734             return;
735         }
736         if (token.name() == "sarcasm") {
737             notImplemented(); // Take a deep breath.
738             return;
739         }
740         if (token.name() == aTag || token.name() == bTag || token.name() == bigTag || token.name() == codeTag || token.name() == emTag || token.name() == fontTag || token.name() == iTag || token.name() == nobrTag || token.name() == sTag || token.name() == smallTag || token.name() == strikeTag || token.name() == strongTag || token.name() == ttTag || token.name() == uTag) {
741             notImplemented();
742             // FIXME: There's a complicated algorithm that goes here.
743             return;
744         }
745         if (token.name() == appletTag || token.name() == marqueeTag || token.name() == objectTag) {
746             if (!m_openElements.inScope(token.name())) {
747                 parseError(token);
748                 return;
749             }
750             generateImpliedEndTags();
751             if (currentElement()->tagQName() != token.name())
752                 parseError(token);
753             m_openElements.popUntil(token.name());
754             m_openElements.pop();
755             m_activeFormattingElements.clearToLastMarker();
756             return;
757         }
758         if (token.name() == brTag) {
759             parseError(token);
760             reconstructTheActiveFormattingElements();
761             // Notice that we lose the attributes.
762             AtomicHTMLToken startBr(HTMLToken::StartTag, token.name());
763             insertSelfClosingElement(startBr);
764             m_framesetOk = false;
765             return;
766         }
767         // FIXME: We need an iterator over m_openElements to implement this
768         // correctly.
769         notImplemented();
770         if (!m_openElements.inScope(token.name()))
771             return;
772         m_openElements.popUntil(token.name());
773         m_openElements.pop();
774         break;
775     case AfterBodyMode:
776         ASSERT(insertionMode() == AfterBodyMode);
777         if (token.name() == htmlTag) {
778             if (m_isParsingFragment) {
779                 parseError(token);
780                 return;
781             }
782             m_insertionMode = AfterAfterBodyMode;
783             return;
784         }
785         m_insertionMode = InBodyMode;
786         processEndTag(token);
787         break;
788     case InHeadNoscriptMode:
789         ASSERT(insertionMode() == InHeadNoscriptMode);
790         if (token.name() == noscriptTag) {
791             ASSERT(currentElement()->tagQName() == noscriptTag);
792             m_openElements.pop();
793             ASSERT(currentElement()->tagQName() == headTag);
794             setInsertionMode(InHeadMode);
795             return;
796         }
797         if (token.name() != brTag) {
798             parseError(token);
799             return;
800         }
801         processDefaultForInHeadNoscriptMode(token);
802         processToken(token);
803         break;
804     case TextMode:
805         if (token.name() == scriptTag) {
806             // Pause ourselves so that parsing stops until the script can be processed by the caller.
807             m_isPaused = true;
808             ASSERT(currentElement()->tagQName() == scriptTag);
809             m_scriptToProcess = currentElement();
810             m_openElements.pop();
811             m_insertionMode = m_originalInsertionMode;
812             return;
813         }
814         m_openElements.pop();
815         m_insertionMode = m_originalInsertionMode;
816         break;
817     default:
818         notImplemented();
819     }
820 }
821
822 void HTMLTreeBuilder::processComment(AtomicHTMLToken& token)
823 {
824     if (m_insertionMode == InitialMode || m_insertionMode == BeforeHTMLMode) {
825         insertCommentOnDocument(token);
826         return;
827     }
828     if (m_insertionMode == AfterBodyMode) {
829         insertCommentOnHTMLHtmlElement(token);
830         return;
831     }
832     insertComment(token);
833 }
834
835 void HTMLTreeBuilder::processCharacter(AtomicHTMLToken& token)
836 {
837     // FIXME: We need to figure out how to handle each character individually.
838     switch (insertionMode()) {
839     case InitialMode:
840         ASSERT(insertionMode() == InitialMode);
841         notImplemented();
842         processDefaultForInitialMode(token);
843         // Fall through.
844     case BeforeHTMLMode:
845         ASSERT(insertionMode() == BeforeHTMLMode);
846         notImplemented();
847         processDefaultForBeforeHTMLMode(token);
848         // Fall through.
849     case BeforeHeadMode:
850         ASSERT(insertionMode() == BeforeHeadMode);
851         notImplemented();
852         processDefaultForBeforeHeadMode(token);
853         // Fall through.
854     case InHeadMode:
855         ASSERT(insertionMode() == InHeadMode);
856         notImplemented();
857         processDefaultForInHeadMode(token);
858         // Fall through.
859     case AfterHeadMode:
860         ASSERT(insertionMode() == AfterHeadMode);
861         notImplemented();
862         processDefaultForAfterHeadMode(token);
863         // Fall through
864     case InBodyMode:
865         ASSERT(insertionMode() == InBodyMode);
866         notImplemented();
867         insertTextNode(token);
868         break;
869     case AfterBodyMode:
870         ASSERT(insertionMode() == AfterBodyMode);
871         m_insertionMode = InBodyMode;
872         processCharacter(token);
873     case TextMode:
874         notImplemented();
875         insertTextNode(token);
876         break;
877     case InHeadNoscriptMode:
878         ASSERT(insertionMode() == InHeadNoscriptMode);
879         processDefaultForInHeadNoscriptMode(token);
880         processToken(token);
881         break;
882     default:
883         notImplemented();
884     }
885 }
886
887 void HTMLTreeBuilder::processEndOfFile(AtomicHTMLToken& token)
888 {
889     switch (insertionMode()) {
890     case InitialMode:
891         ASSERT(insertionMode() == InitialMode);
892         processDefaultForInitialMode(token);
893         // Fall through.
894     case BeforeHTMLMode:
895         ASSERT(insertionMode() == BeforeHTMLMode);
896         processDefaultForBeforeHTMLMode(token);
897         // Fall through.
898     case BeforeHeadMode:
899         ASSERT(insertionMode() == BeforeHeadMode);
900         processDefaultForBeforeHeadMode(token);
901         // Fall through.
902     case InHeadMode:
903         ASSERT(insertionMode() == InHeadMode);
904         processDefaultForInHeadMode(token);
905         // Fall through.
906     case AfterHeadMode:
907         ASSERT(insertionMode() == AfterHeadMode);
908         processDefaultForAfterHeadMode(token);
909         // Fall through
910     case InBodyMode:
911         ASSERT(insertionMode() == InBodyMode);
912         notImplemented();
913         break;
914     case AfterBodyMode:
915         ASSERT(insertionMode() == AfterBodyMode);
916         notImplemented();
917         break;
918     case InHeadNoscriptMode:
919         ASSERT(insertionMode() == InHeadNoscriptMode);
920         processDefaultForInHeadNoscriptMode(token);
921         processToken(token);
922         break;
923     default:
924         notImplemented();
925     }
926 }
927
928 void HTMLTreeBuilder::processDefaultForInitialMode(AtomicHTMLToken& token)
929 {
930     notImplemented();
931     parseError(token);
932     setInsertionMode(BeforeHTMLMode);
933 }
934
935 void HTMLTreeBuilder::processDefaultForBeforeHTMLMode(AtomicHTMLToken&)
936 {
937     AtomicHTMLToken startHTML(HTMLToken::StartTag, htmlTag.localName());
938     insertHTMLStartTagBeforeHTML(startHTML);
939     setInsertionMode(BeforeHeadMode);
940 }
941
942 void HTMLTreeBuilder::processDefaultForBeforeHeadMode(AtomicHTMLToken&)
943 {
944     AtomicHTMLToken startHead(HTMLToken::StartTag, headTag.localName());
945     processStartTag(startHead);
946 }
947
948 void HTMLTreeBuilder::processDefaultForInHeadMode(AtomicHTMLToken&)
949 {
950     AtomicHTMLToken endHead(HTMLToken::EndTag, headTag.localName());
951     processEndTag(endHead);
952 }
953
954 void HTMLTreeBuilder::processDefaultForInHeadNoscriptMode(AtomicHTMLToken&)
955 {
956     AtomicHTMLToken endNoscript(HTMLToken::EndTag, noscriptTag.localName());
957     processEndTag(endNoscript);
958 }
959
960 void HTMLTreeBuilder::processDefaultForAfterHeadMode(AtomicHTMLToken&)
961 {
962     AtomicHTMLToken startBody(HTMLToken::StartTag, bodyTag.localName());
963     processStartTag(startBody);
964     m_framesetOk = true;
965 }
966
967 bool HTMLTreeBuilder::processStartTagForInHead(AtomicHTMLToken& token)
968 {
969     if (token.name() == htmlTag) {
970         insertHTMLStartTagInBody(token);
971         return true;
972     }
973     // FIXME: Atomize "command".
974     if (token.name() == baseTag || token.name() == "command" || token.name() == linkTag || token.name() == metaTag) {
975         insertSelfClosingElement(token);
976         // Note: The custom processing for the <meta> tag is done in HTMLMetaElement::process().
977         return true;
978     }
979     if (token.name() == titleTag) {
980         insertGenericRCDATAElement(token);
981         return true;
982     }
983     if (token.name() == noscriptTag) {
984         if (isScriptingFlagEnabled(m_document->frame())) {
985             insertGenericRawTextElement(token);
986             return true;
987         }
988         insertElement(token);
989         setInsertionMode(InHeadNoscriptMode);
990         return true;
991     }
992     if (token.name() == noframesTag || token.name() == styleTag) {
993         insertGenericRawTextElement(token);
994         return true;
995     }
996     if (token.name() == scriptTag) {
997         insertScriptElement(token);
998         return true;
999     }
1000     if (token.name() == headTag) {
1001         parseError(token);
1002         return true;
1003     }
1004     return false;
1005 }
1006
1007 void HTMLTreeBuilder::insertDoctype(AtomicHTMLToken& token)
1008 {
1009     ASSERT(token.type() == HTMLToken::DOCTYPE);
1010     attach(m_document, DocumentType::create(m_document, token.name(), String::adopt(token.publicIdentifier()), String::adopt(token.systemIdentifier())));
1011     // FIXME: Move quirks mode detection from DocumentType element to here.
1012     notImplemented();
1013     if (token.forceQuirks())
1014         m_document->setParseMode(Document::Compat);
1015 }
1016
1017 void HTMLTreeBuilder::insertComment(AtomicHTMLToken& token)
1018 {
1019     ASSERT(token.type() == HTMLToken::Comment);
1020     attach(currentElement(), Comment::create(m_document, token.comment()));
1021 }
1022
1023 void HTMLTreeBuilder::insertCommentOnDocument(AtomicHTMLToken& token)
1024 {
1025     ASSERT(token.type() == HTMLToken::Comment);
1026     attach(m_document, Comment::create(m_document, token.comment()));
1027 }
1028
1029 void HTMLTreeBuilder::insertCommentOnHTMLHtmlElement(AtomicHTMLToken& token)
1030 {
1031     ASSERT(token.type() == HTMLToken::Comment);
1032     attach(m_openElements.htmlElement(), Comment::create(m_document, token.comment()));
1033 }
1034
1035 PassRefPtr<Element> HTMLTreeBuilder::createElementAndAttachToCurrent(AtomicHTMLToken& token)
1036 {
1037     ASSERT(token.type() == HTMLToken::StartTag);
1038     return attach(currentElement(), createElement(token));
1039 }
1040
1041 void HTMLTreeBuilder::insertHTMLHtmlElement(AtomicHTMLToken& token)
1042 {
1043     m_openElements.pushHTMLHtmlElement(createElementAndAttachToCurrent(token));
1044 }
1045
1046 void HTMLTreeBuilder::insertHTMLHeadElement(AtomicHTMLToken& token)
1047 {
1048     m_headElement = createElementAndAttachToCurrent(token);
1049     m_openElements.pushHTMLHeadElement(m_headElement);
1050 }
1051
1052 void HTMLTreeBuilder::insertHTMLBodyElement(AtomicHTMLToken& token)
1053 {
1054     m_openElements.pushHTMLBodyElement(createElementAndAttachToCurrent(token));
1055 }
1056
1057 void HTMLTreeBuilder::insertElement(AtomicHTMLToken& token)
1058 {
1059     m_openElements.push(createElementAndAttachToCurrent(token));
1060 }
1061
1062 void HTMLTreeBuilder::insertSelfClosingElement(AtomicHTMLToken& token)
1063 {
1064     ASSERT(token.type() == HTMLToken::StartTag);
1065     attach(currentElement(), createElement(token));
1066     // FIXME: Do we want to acknowledge the token's self-closing flag?
1067     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#acknowledge-self-closing-flag
1068 }
1069
1070 void HTMLTreeBuilder::insertFormattingElement(AtomicHTMLToken& token)
1071 {
1072     // http://www.whatwg.org/specs/web-apps/current-work/multipage/parsing.html#the-stack-of-open-elements
1073     // Possible active formatting elements include:
1074     // a, b, big, code, em, font, i, nobr, s, small, strike, strong, tt, and u.
1075     insertElement(token);
1076     m_activeFormattingElements.append(currentElement());
1077 }
1078
1079 void HTMLTreeBuilder::insertGenericRCDATAElement(AtomicHTMLToken& token)
1080 {
1081     insertElement(token);
1082     m_tokenizer->setState(HTMLTokenizer::RCDATAState);
1083     m_originalInsertionMode = m_insertionMode;
1084     m_insertionMode = TextMode;
1085 }
1086
1087 void HTMLTreeBuilder::insertGenericRawTextElement(AtomicHTMLToken& token)
1088 {
1089     insertElement(token);
1090     m_tokenizer->setState(HTMLTokenizer::RAWTEXTState);
1091     m_originalInsertionMode = m_insertionMode;
1092     m_insertionMode = TextMode;
1093 }
1094
1095 void HTMLTreeBuilder::insertScriptElement(AtomicHTMLToken& token)
1096 {
1097     ASSERT_UNUSED(token, token.type() == HTMLToken::StartTag);
1098     RefPtr<HTMLScriptElement> element = HTMLScriptElement::create(scriptTag, m_document, true);
1099     element->setAttributeMap(token.attributes(), m_fragmentScriptingPermission);
1100     m_openElements.push(attach(currentElement(), element.release()));
1101     m_tokenizer->setState(HTMLTokenizer::ScriptDataState);
1102     m_originalInsertionMode = m_insertionMode;
1103     m_insertionMode = TextMode;
1104 }
1105
1106 void HTMLTreeBuilder::insertTextNode(AtomicHTMLToken& token)
1107 {
1108     attach(currentElement(), Text::create(m_document, token.characters()));
1109 }
1110     
1111 PassRefPtr<Element> HTMLTreeBuilder::createElement(AtomicHTMLToken& token)
1112 {
1113     RefPtr<Element> element = HTMLElementFactory::createHTMLElement(QualifiedName(nullAtom, token.name(), xhtmlNamespaceURI), m_document, 0);
1114     element->setAttributeMap(token.attributes(), m_fragmentScriptingPermission);
1115     return element.release();
1116 }
1117
1118 bool HTMLTreeBuilder::indexOfFirstUnopenFormattingElement(unsigned& firstUnopenElementIndex) const
1119 {
1120     if (m_activeFormattingElements.isEmpty())
1121         return false;
1122     unsigned index = m_activeFormattingElements.size();
1123     do {
1124         --index;
1125         const HTMLFormattingElementList::Entry& entry = m_activeFormattingElements[index];
1126         if (entry.isMarker() || m_openElements.contains(entry.element())) {
1127             firstUnopenElementIndex = index;
1128             return true;
1129         }
1130     } while (index);
1131     return false;
1132 }
1133
1134 void HTMLTreeBuilder::reconstructTheActiveFormattingElements()
1135 {
1136     unsigned firstUnopenElementIndex;
1137     if (!indexOfFirstUnopenFormattingElement(firstUnopenElementIndex))
1138         return;
1139
1140     unsigned unopenEntryIndex = firstUnopenElementIndex;
1141     ASSERT(unopenEntryIndex < m_activeFormattingElements.size());
1142     for (; unopenEntryIndex < m_activeFormattingElements.size(); ++unopenEntryIndex) {
1143         HTMLFormattingElementList::Entry& unopenedEntry = m_activeFormattingElements[unopenEntryIndex];
1144         // FIXME: We're supposed to save the original token in the entry.
1145         AtomicHTMLToken fakeToken(HTMLToken::StartTag, unopenedEntry.element()->localName());
1146         insertElement(fakeToken);
1147         unopenedEntry.replaceElement(currentElement());
1148     }
1149 }
1150
1151 namespace {
1152
1153 bool hasImpliedEndTag(Element* element)
1154 {
1155     return element->hasTagName(ddTag)
1156         || element->hasTagName(dtTag)
1157         || element->hasTagName(liTag)
1158         || element->hasTagName(optionTag)
1159         || element->hasTagName(optgroupTag)
1160         || element->hasTagName(pTag)
1161         || element->hasTagName(rpTag)
1162         || element->hasTagName(rtTag);
1163 }
1164
1165 }
1166
1167 void HTMLTreeBuilder::generateImpliedEndTagsWithExclusion(const AtomicString& tagName)
1168 {
1169     while (hasImpliedEndTag(currentElement()) && !currentElement()->hasLocalName(tagName))
1170         m_openElements.pop();
1171 }
1172
1173 void HTMLTreeBuilder::generateImpliedEndTags()
1174 {
1175     while (hasImpliedEndTag(currentElement()))
1176         m_openElements.pop();
1177 }
1178
1179 void HTMLTreeBuilder::finished()
1180 {
1181     // We should call m_document->finishedParsing() here, except
1182     // m_legacyTreeBuilder->finished() does it for us.
1183     if (m_legacyTreeBuilder) {
1184         m_legacyTreeBuilder->finished();
1185         return;
1186     }
1187
1188     AtomicHTMLToken eofToken(HTMLToken::EndOfFile, nullAtom);
1189     processToken(eofToken);
1190
1191     // Warning, this may delete the parser, so don't try to do anything else after this.
1192     if (!m_isParsingFragment)
1193         m_document->finishedParsing();
1194 }
1195
1196 bool HTMLTreeBuilder::isScriptingFlagEnabled(Frame* frame)
1197 {
1198     if (!frame)
1199         return false;
1200     if (ScriptController* scriptController = frame->script())
1201         return scriptController->canExecuteScripts(NotAboutToExecuteScript);
1202     return false;
1203 }
1204
1205 }