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