0ee89f15250328123c7f0418652c18e349832031
[WebKit.git] / Source / WebCore / html / parser / HTMLConstructionSite.cpp
1 /*
2  * Copyright (C) 2010 Google, Inc. All Rights Reserved.
3  * Copyright (C) 2011 Apple Inc. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY GOOGLE INC. ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL GOOGLE INC. OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 #include "config.h"
28 #include "HTMLTreeBuilder.h"
29
30 #include "Comment.h"
31 #include "DocumentFragment.h"
32 #include "DocumentType.h"
33 #include "Element.h"
34 #include "Frame.h"
35 #include "HTMLDocument.h"
36 #include "HTMLElementFactory.h"
37 #include "HTMLFormElement.h"
38 #include "HTMLHtmlElement.h"
39 #include "HTMLNames.h"
40 #include "HTMLParserIdioms.h"
41 #include "HTMLScriptElement.h"
42 #include "HTMLToken.h"
43 #include "HTMLTokenizer.h"
44 #include "LocalizedStrings.h"
45 #if ENABLE(MATHML)
46 #include "MathMLNames.h"
47 #endif
48 #include "NotImplemented.h"
49 #if ENABLE(SVG)
50 #include "SVGNames.h"
51 #endif
52 #include "Settings.h"
53 #include "Text.h"
54 #include <wtf/UnusedParam.h>
55
56 namespace WebCore {
57
58 using namespace HTMLNames;
59
60 namespace {
61
62 bool hasImpliedEndTag(ContainerNode* node)
63 {
64     return node->hasTagName(ddTag)
65         || node->hasTagName(dtTag)
66         || node->hasTagName(liTag)
67         || node->hasTagName(optionTag)
68         || node->hasTagName(optgroupTag)
69         || node->hasTagName(pTag)
70         || node->hasTagName(rpTag)
71         || node->hasTagName(rtTag);
72 }
73
74 bool causesFosterParenting(const QualifiedName& tagName)
75 {
76     return tagName == tableTag
77         || tagName == tbodyTag
78         || tagName == tfootTag
79         || tagName == theadTag
80         || tagName == trTag;
81 }
82
83 inline bool isAllWhitespace(const String& string)
84 {
85     return string.isAllSpecialCharacters<isHTMLSpace>();
86 }
87
88 } // namespace
89
90 static inline void executeTask(HTMLConstructionSiteTask& task)
91 {
92     if (task.nextChild)
93         task.parent->parserInsertBefore(task.child.get(), task.nextChild.get());
94     else
95         task.parent->parserAddChild(task.child.get());
96
97     // JavaScript run from beforeload (or DOM Mutation or event handlers)
98     // might have removed the child, in which case we should not attach it.
99
100     if (task.child->parentNode() && task.parent->attached() && !task.child->attached())
101         task.child->attach();
102
103     task.child->beginParsingChildren();
104
105     if (task.selfClosing)
106         task.child->finishParsingChildren();
107 }
108
109 void HTMLConstructionSite::attachLater(ContainerNode* parent, PassRefPtr<Node> prpChild)
110 {
111     HTMLConstructionSiteTask task;
112     task.parent = parent;
113     task.child = prpChild;
114
115     if (shouldFosterParent()) {
116         fosterParent(task.child);
117         return;
118     }
119
120     // Add as a sibling of the parent if we have reached the maximum depth allowed.
121     if (m_openElements.stackDepth() > m_maximumDOMTreeDepth && task.parent->parentNode())
122         task.parent = task.parent->parentNode();
123
124     ASSERT(task.parent);
125     m_attachmentQueue.append(task);
126 }
127
128 void HTMLConstructionSite::executeQueuedTasks()
129 {
130     const size_t size = m_attachmentQueue.size();
131     if (!size)
132         return;
133
134     // Copy the task queue into a local variable in case executeTask
135     // re-enters the parser.
136     AttachmentQueue queue;
137     queue.swap(m_attachmentQueue);
138
139     for (size_t i = 0; i < size; ++i)
140         executeTask(queue[i]);
141
142     // We might be detached now.
143 }
144
145 HTMLConstructionSite::HTMLConstructionSite(Document* document, unsigned maximumDOMTreeDepth)
146     : m_document(document)
147     , m_attachmentRoot(document)
148     , m_fragmentScriptingPermission(FragmentScriptingAllowed)
149     , m_isParsingFragment(false)
150     , m_redirectAttachToFosterParent(false)
151     , m_maximumDOMTreeDepth(maximumDOMTreeDepth)
152 {
153 }
154
155 HTMLConstructionSite::HTMLConstructionSite(DocumentFragment* fragment, FragmentScriptingPermission scriptingPermission, unsigned maximumDOMTreeDepth)
156     : m_document(fragment->document())
157     , m_attachmentRoot(fragment)
158     , m_fragmentScriptingPermission(scriptingPermission)
159     , m_isParsingFragment(true)
160     , m_redirectAttachToFosterParent(false)
161     , m_maximumDOMTreeDepth(maximumDOMTreeDepth)
162 {
163 }
164
165 HTMLConstructionSite::~HTMLConstructionSite()
166 {
167 }
168
169 void HTMLConstructionSite::detach()
170 {
171     m_document = 0;
172     m_attachmentRoot = 0;
173 }
174
175 void HTMLConstructionSite::setForm(HTMLFormElement* form)
176 {
177     // This method should only be needed for HTMLTreeBuilder in the fragment case.
178     ASSERT(!m_form);
179     m_form = form;
180 }
181
182 PassRefPtr<HTMLFormElement> HTMLConstructionSite::takeForm()
183 {
184     return m_form.release();
185 }
186
187 void HTMLConstructionSite::dispatchDocumentElementAvailableIfNeeded()
188 {
189     ASSERT(m_document);
190     if (m_document->frame() && !m_isParsingFragment)
191         m_document->frame()->loader()->dispatchDocumentElementAvailable();
192 }
193
194 void HTMLConstructionSite::insertHTMLHtmlStartTagBeforeHTML(AtomicHTMLToken& token)
195 {
196     RefPtr<HTMLHtmlElement> element = HTMLHtmlElement::create(m_document);
197     element->parserSetAttributeMap(token.takeAttributes(), m_fragmentScriptingPermission);
198     attachLater(m_attachmentRoot, element);
199     m_openElements.pushHTMLHtmlElement(element);
200
201     executeQueuedTasks();
202     element->insertedByParser();
203     dispatchDocumentElementAvailableIfNeeded();
204 }
205
206 void HTMLConstructionSite::mergeAttributesFromTokenIntoElement(AtomicHTMLToken& token, Element* element)
207 {
208     if (!token.attributes())
209         return;
210
211     NamedNodeMap* attributes = element->ensureUpdatedAttributes();
212     for (unsigned i = 0; i < token.attributes()->length(); ++i) {
213         Attribute* attribute = token.attributes()->attributeItem(i);
214         if (!attributes->getAttributeItem(attribute->name()))
215             element->setAttribute(attribute->name(), attribute->value());
216     }
217 }
218
219 void HTMLConstructionSite::insertHTMLHtmlStartTagInBody(AtomicHTMLToken& token)
220 {
221     // FIXME: parse error
222
223     // Fragments do not have a root HTML element, so any additional HTML elements
224     // encountered during fragment parsing should be ignored.
225     if (m_isParsingFragment)
226         return;
227
228     mergeAttributesFromTokenIntoElement(token, m_openElements.htmlElement());
229 }
230
231 void HTMLConstructionSite::insertHTMLBodyStartTagInBody(AtomicHTMLToken& token)
232 {
233     // FIXME: parse error
234     mergeAttributesFromTokenIntoElement(token, m_openElements.bodyElement());
235 }
236
237 void HTMLConstructionSite::insertDoctype(AtomicHTMLToken& token)
238 {
239     ASSERT(token.type() == HTMLTokenTypes::DOCTYPE);
240
241     RefPtr<DocumentType> doctype = DocumentType::create(m_document, token.name(), String::adopt(token.publicIdentifier()), String::adopt(token.systemIdentifier()));
242     attachLater(m_attachmentRoot, doctype.release());
243
244     // DOCTYPE nodes are only processed when parsing fragments w/o contextElements, which
245     // never occurs.  However, if we ever chose to support such, this code is subtly wrong,
246     // because context-less fragments can determine their own quirks mode, and thus change
247     // parsing rules (like <p> inside <table>).  For now we ASSERT that we never hit this code
248     // in a fragment, as changing the owning document's compatibility mode would be wrong.
249     ASSERT(!m_isParsingFragment);
250     if (m_isParsingFragment)
251         return;
252
253     if (token.forceQuirks())
254         m_document->setCompatibilityMode(Document::QuirksMode);
255     else {
256         // We need to actually add the Doctype node to the DOM.
257         executeQueuedTasks();
258         m_document->setCompatibilityModeFromDoctype();
259     }
260 }
261
262 void HTMLConstructionSite::insertComment(AtomicHTMLToken& token)
263 {
264     ASSERT(token.type() == HTMLTokenTypes::Comment);
265     attachLater(currentNode(), Comment::create(currentNode()->document(), token.comment()));
266 }
267
268 void HTMLConstructionSite::insertCommentOnDocument(AtomicHTMLToken& token)
269 {
270     ASSERT(token.type() == HTMLTokenTypes::Comment);
271     attachLater(m_attachmentRoot, Comment::create(m_document, token.comment()));
272 }
273
274 void HTMLConstructionSite::insertCommentOnHTMLHtmlElement(AtomicHTMLToken& token)
275 {
276     ASSERT(token.type() == HTMLTokenTypes::Comment);
277     ContainerNode* parent = m_openElements.rootNode();
278     attachLater(parent, Comment::create(parent->document(), token.comment()));
279 }
280
281 void HTMLConstructionSite::insertHTMLHeadElement(AtomicHTMLToken& token)
282 {
283     ASSERT(!shouldFosterParent());
284     m_head = createHTMLElement(token);
285     attachLater(currentNode(), m_head);
286     m_openElements.pushHTMLHeadElement(m_head);
287 }
288
289 void HTMLConstructionSite::insertHTMLBodyElement(AtomicHTMLToken& token)
290 {
291     ASSERT(!shouldFosterParent());
292     RefPtr<Element> body = createHTMLElement(token);
293     attachLater(currentNode(), body);
294     m_openElements.pushHTMLBodyElement(body.release());
295 }
296
297 void HTMLConstructionSite::insertHTMLFormElement(AtomicHTMLToken& token, bool isDemoted)
298 {
299     RefPtr<Element> element = createHTMLElement(token);
300     ASSERT(element->hasTagName(formTag));
301     m_form = static_pointer_cast<HTMLFormElement>(element.release());
302     m_form->setDemoted(isDemoted);
303     attachLater(currentNode(), m_form);
304     m_openElements.push(m_form);
305 }
306
307 void HTMLConstructionSite::insertHTMLElement(AtomicHTMLToken& token)
308 {
309     RefPtr<Element> element = createHTMLElement(token);
310     attachLater(currentNode(), element);
311     m_openElements.push(element.release());
312 }
313
314 void HTMLConstructionSite::insertSelfClosingHTMLElement(AtomicHTMLToken& token)
315 {
316     ASSERT(token.type() == HTMLTokenTypes::StartTag);
317     attachLater(currentNode(), createHTMLElement(token));
318     // Normally HTMLElementStack is responsible for calling finishParsingChildren,
319     // but self-closing elements are never in the element stack so the stack
320     // doesn't get a chance to tell them that we're done parsing their children.
321     m_attachmentQueue.last().selfClosing = true;
322     // FIXME: Do we want to acknowledge the token's self-closing flag?
323     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#acknowledge-self-closing-flag
324 }
325
326 void HTMLConstructionSite::insertFormattingElement(AtomicHTMLToken& token)
327 {
328     // http://www.whatwg.org/specs/web-apps/current-work/multipage/parsing.html#the-stack-of-open-elements
329     // Possible active formatting elements include:
330     // a, b, big, code, em, font, i, nobr, s, small, strike, strong, tt, and u.
331     insertHTMLElement(token);
332     m_activeFormattingElements.append(currentElement());
333 }
334
335 void HTMLConstructionSite::insertScriptElement(AtomicHTMLToken& token)
336 {
337     RefPtr<HTMLScriptElement> element = HTMLScriptElement::create(scriptTag, currentNode()->document(), true);
338     if (m_fragmentScriptingPermission == FragmentScriptingAllowed)
339         element->parserSetAttributeMap(token.takeAttributes(), m_fragmentScriptingPermission);
340     attachLater(currentNode(), element);
341     m_openElements.push(element.release());
342 }
343
344 void HTMLConstructionSite::insertForeignElement(AtomicHTMLToken& token, const AtomicString& namespaceURI)
345 {
346     ASSERT(token.type() == HTMLTokenTypes::StartTag);
347     notImplemented(); // parseError when xmlns or xmlns:xlink are wrong.
348
349     RefPtr<Element> element = createElement(token, namespaceURI);
350     attachLater(currentNode(), element);
351     // FIXME: Don't we need to set the selfClosing flag on the task if we're
352     // not going to push the element on to the stack of open elements?
353     if (!token.selfClosing())
354         m_openElements.push(element.release());
355 }
356
357 void HTMLConstructionSite::insertTextNode(const String& characters, WhitespaceMode whitespaceMode)
358 {
359     HTMLConstructionSiteTask task;
360     task.parent = currentNode();
361
362     if (shouldFosterParent())
363         findFosterSite(task);
364
365     // Strings composed entirely of whitespace are likely to be repeated.
366     // Turn them into AtomicString so we share a single string for each.
367     bool shouldUseAtomicString = whitespaceMode == AllWhitespace
368         || (whitespaceMode == WhitespaceUnknown && isAllWhitespace(characters));
369
370     unsigned currentPosition = 0;
371
372     // FIXME: Splitting text nodes into smaller chunks contradicts HTML5 spec, but is currently necessary
373     // for performance, see <https://bugs.webkit.org/show_bug.cgi?id=55898>.
374
375     Node* previousChild = task.nextChild ? task.nextChild->previousSibling() : task.parent->lastChild();
376     if (previousChild && previousChild->isTextNode()) {
377         // FIXME: We're only supposed to append to this text node if it
378         // was the last text node inserted by the parser.
379         CharacterData* textNode = static_cast<CharacterData*>(previousChild);
380         currentPosition = textNode->parserAppendData(characters.characters(), characters.length(), Text::defaultLengthLimit);
381     }
382
383     while (currentPosition < characters.length()) {
384         RefPtr<Text> textNode = Text::createWithLengthLimit(task.parent->document(), shouldUseAtomicString ? AtomicString(characters).string() : characters, currentPosition);
385         // If we have a whole string of unbreakable characters the above could lead to an infinite loop. Exceeding the length limit is the lesser evil.
386         if (!textNode->length()) {
387             String substring = characters.substring(currentPosition);
388             textNode = Text::create(task.parent->document(), shouldUseAtomicString ? AtomicString(substring).string() : substring);
389         }
390
391         currentPosition += textNode->length();
392         ASSERT(currentPosition <= characters.length());
393         task.child = textNode.release();
394         executeTask(task);
395     }
396 }
397
398 PassRefPtr<Element> HTMLConstructionSite::createElement(AtomicHTMLToken& token, const AtomicString& namespaceURI)
399 {
400     QualifiedName tagName(nullAtom, token.name(), namespaceURI);
401     RefPtr<Element> element = currentNode()->document()->createElement(tagName, true);
402     element->parserSetAttributeMap(token.takeAttributes(), m_fragmentScriptingPermission);
403     return element.release();
404 }
405
406 PassRefPtr<Element> HTMLConstructionSite::createHTMLElement(AtomicHTMLToken& token)
407 {
408     QualifiedName tagName(nullAtom, token.name(), xhtmlNamespaceURI);
409     // FIXME: This can't use HTMLConstructionSite::createElement because we
410     // have to pass the current form element.  We should rework form association
411     // to occur after construction to allow better code sharing here.
412     RefPtr<Element> element = HTMLElementFactory::createHTMLElement(tagName, currentNode()->document(), form(), true);
413     element->parserSetAttributeMap(token.takeAttributes(), m_fragmentScriptingPermission);
414     ASSERT(element->isHTMLElement());
415     return element.release();
416 }
417
418 PassRefPtr<Element> HTMLConstructionSite::createHTMLElementFromElementRecord(HTMLElementStack::ElementRecord* record)
419 {
420     return createHTMLElementFromSavedElement(record->element());
421 }
422
423 namespace {
424
425 // FIXME: Move this function to the top of the file.
426 inline PassOwnPtr<NamedNodeMap> cloneAttributes(Element* element)
427 {
428     NamedNodeMap* attributes = element->updatedAttributes();
429     if (!attributes)
430         return nullptr;
431
432     OwnPtr<NamedNodeMap> newAttributes = NamedNodeMap::create();
433     for (size_t i = 0; i < attributes->length(); ++i) {
434         Attribute* attribute = attributes->attributeItem(i);
435         RefPtr<Attribute> clone = Attribute::createMapped(attribute->name(), attribute->value());
436         newAttributes->addAttribute(clone);
437     }
438     return newAttributes.release();
439 }
440
441 } // namespace
442
443 PassRefPtr<Element> HTMLConstructionSite::createHTMLElementFromSavedElement(Element* element)
444 {
445     // FIXME: This method is wrong.  We should be using the original token.
446     // Using an Element* causes us to fail examples like this:
447     // <b id="1"><p><script>document.getElementById("1").id = "2"</script></p>TEXT</b>
448     // When reconstructTheActiveFormattingElements calls this method to open
449     // a second <b> tag to wrap TEXT, it will have id "2", even though the HTML5
450     // spec implies it should be "1".  Minefield matches the HTML5 spec here.
451
452     ASSERT(element->isHTMLElement()); // otherwise localName() might be wrong.
453     AtomicHTMLToken fakeToken(HTMLTokenTypes::StartTag, element->localName(), cloneAttributes(element));
454     return createHTMLElement(fakeToken);
455 }
456
457 bool HTMLConstructionSite::indexOfFirstUnopenFormattingElement(unsigned& firstUnopenElementIndex) const
458 {
459     if (m_activeFormattingElements.isEmpty())
460         return false;
461     unsigned index = m_activeFormattingElements.size();
462     do {
463         --index;
464         const HTMLFormattingElementList::Entry& entry = m_activeFormattingElements.at(index);
465         if (entry.isMarker() || m_openElements.contains(entry.element())) {
466             firstUnopenElementIndex = index + 1;
467             return firstUnopenElementIndex < m_activeFormattingElements.size();
468         }
469     } while (index);
470     firstUnopenElementIndex = index;
471     return true;
472 }
473
474 void HTMLConstructionSite::reconstructTheActiveFormattingElements()
475 {
476     unsigned firstUnopenElementIndex;
477     if (!indexOfFirstUnopenFormattingElement(firstUnopenElementIndex))
478         return;
479
480     unsigned unopenEntryIndex = firstUnopenElementIndex;
481     ASSERT(unopenEntryIndex < m_activeFormattingElements.size());
482     for (; unopenEntryIndex < m_activeFormattingElements.size(); ++unopenEntryIndex) {
483         HTMLFormattingElementList::Entry& unopenedEntry = m_activeFormattingElements.at(unopenEntryIndex);
484         RefPtr<Element> reconstructed = createHTMLElementFromSavedElement(unopenedEntry.element());
485         attachLater(currentNode(), reconstructed);
486         m_openElements.push(reconstructed.release());
487         unopenedEntry.replaceElement(currentElement());
488     }
489 }
490
491 void HTMLConstructionSite::generateImpliedEndTagsWithExclusion(const AtomicString& tagName)
492 {
493     while (hasImpliedEndTag(currentNode()) && !currentNode()->hasLocalName(tagName))
494         m_openElements.pop();
495 }
496
497 void HTMLConstructionSite::generateImpliedEndTags()
498 {
499     while (hasImpliedEndTag(currentNode()))
500         m_openElements.pop();
501 }
502
503 void HTMLConstructionSite::findFosterSite(HTMLConstructionSiteTask& task)
504 {
505     HTMLElementStack::ElementRecord* lastTableElementRecord = m_openElements.topmost(tableTag.localName());
506     if (lastTableElementRecord) {
507         Element* lastTableElement = lastTableElementRecord->element();
508         if (ContainerNode* parent = lastTableElement->parentNode()) {
509             task.parent = parent;
510             task.nextChild = lastTableElement;
511             return;
512         }
513         task.parent = lastTableElementRecord->next()->element();
514         return;
515     }
516     // Fragment case
517     task.parent = m_openElements.rootNode(); // DocumentFragment
518 }
519
520 bool HTMLConstructionSite::shouldFosterParent() const
521 {
522     return m_redirectAttachToFosterParent
523         && currentNode()->isElementNode()
524         && causesFosterParenting(currentElement()->tagQName());
525 }
526
527 void HTMLConstructionSite::fosterParent(PassRefPtr<Node> node)
528 {
529     HTMLConstructionSiteTask task;
530     findFosterSite(task);
531     task.child = node;
532     ASSERT(task.parent);
533     m_attachmentQueue.append(task);
534 }
535
536 }