9cc3a03166e511ab258672f43cb700815c774024
[WebKit-https.git] / Source / WebCore / html / parser / HTMLElementStack.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 "HTMLElementStack.h"
29
30 #include "DocumentFragment.h"
31 #include "Element.h"
32 #include "HTMLNames.h"
33 #include "MathMLNames.h"
34 #include "SVGNames.h"
35 #include <wtf/PassOwnPtr.h>
36
37 namespace WebCore {
38
39 using namespace HTMLNames;
40
41 namespace {
42
43 inline bool isNumberedHeaderElement(ContainerNode* node)
44 {
45     return node->hasTagName(h1Tag)
46         || node->hasTagName(h2Tag)
47         || node->hasTagName(h3Tag)
48         || node->hasTagName(h4Tag)
49         || node->hasTagName(h5Tag)
50         || node->hasTagName(h6Tag);
51 }
52     
53 inline bool isRootNode(ContainerNode* node)
54 {
55     return node->nodeType() == Node::DOCUMENT_FRAGMENT_NODE
56         || node->hasTagName(htmlTag);
57 }
58
59 inline bool isScopeMarker(ContainerNode* node)
60 {
61     return node->hasTagName(appletTag)
62         || node->hasTagName(captionTag)
63         || node->hasTagName(marqueeTag)
64         || node->hasTagName(objectTag)
65         || node->hasTagName(tableTag)
66         || node->hasTagName(tdTag)
67         || node->hasTagName(thTag)
68         || node->hasTagName(MathMLNames::miTag)
69         || node->hasTagName(MathMLNames::moTag)
70         || node->hasTagName(MathMLNames::mnTag)
71         || node->hasTagName(MathMLNames::msTag)
72         || node->hasTagName(MathMLNames::mtextTag)
73         || node->hasTagName(MathMLNames::annotation_xmlTag)
74         || node->hasTagName(SVGNames::foreignObjectTag)
75         || node->hasTagName(SVGNames::descTag)
76         || node->hasTagName(SVGNames::titleTag)
77         || isRootNode(node);
78 }
79
80 inline bool isListItemScopeMarker(ContainerNode* node)
81 {
82     return isScopeMarker(node)
83         || node->hasTagName(olTag)
84         || node->hasTagName(ulTag);
85 }
86
87 inline bool isTableScopeMarker(ContainerNode* node)
88 {
89     return node->hasTagName(tableTag)
90         || isRootNode(node);
91 }
92
93 inline bool isTableBodyScopeMarker(ContainerNode* node)
94 {
95     return node->hasTagName(tbodyTag)
96         || node->hasTagName(tfootTag)
97         || node->hasTagName(theadTag)
98         || isRootNode(node);
99 }
100
101 inline bool isTableRowScopeMarker(ContainerNode* node)
102 {
103     return node->hasTagName(trTag)
104         || isRootNode(node);
105 }
106
107 inline bool isForeignContentScopeMarker(ContainerNode* node)
108 {
109     return HTMLElementStack::isMathMLTextIntegrationPoint(node)
110         || HTMLElementStack::isHTMLIntegrationPoint(node)
111         || isInHTMLNamespace(node);
112 }
113
114 inline bool isButtonScopeMarker(ContainerNode* node)
115 {
116     return isScopeMarker(node)
117         || node->hasTagName(buttonTag);
118 }
119
120 inline bool isSelectScopeMarker(ContainerNode* node)
121 {
122     return !node->hasTagName(optgroupTag)
123         && !node->hasTagName(optionTag);
124 }
125
126 }
127
128 HTMLElementStack::ElementRecord::ElementRecord(PassRefPtr<ContainerNode> node, PassOwnPtr<ElementRecord> next)
129     : m_node(node)
130     , m_next(next)
131 {
132     ASSERT(m_node);
133 }
134
135 HTMLElementStack::ElementRecord::~ElementRecord()
136 {
137 }
138
139 void HTMLElementStack::ElementRecord::replaceElement(PassRefPtr<Element> element)
140 {
141     ASSERT(element);
142     ASSERT(!m_node || m_node->isElementNode());
143     // FIXME: Should this call finishParsingChildren?
144     m_node = element;
145 }
146
147 bool HTMLElementStack::ElementRecord::isAbove(ElementRecord* other) const
148 {
149     for (ElementRecord* below = next(); below; below = below->next()) {
150         if (below == other)
151             return true;
152     }
153     return false;
154 }
155
156 HTMLElementStack::HTMLElementStack()
157     : m_rootNode(0)
158     , m_headElement(0)
159     , m_bodyElement(0)
160     , m_stackDepth(0)
161 {
162 }
163
164 HTMLElementStack::~HTMLElementStack()
165 {
166 }
167
168 bool HTMLElementStack::hasOnlyOneElement() const
169 {
170     return !topRecord()->next();
171 }
172
173 bool HTMLElementStack::secondElementIsHTMLBodyElement() const
174 {
175     // This is used the fragment case of <body> and <frameset> in the "in body"
176     // insertion mode.
177     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#parsing-main-inbody
178     ASSERT(m_rootNode);
179     // If we have a body element, it must always be the second element on the
180     // stack, as we always start with an html element, and any other element
181     // would cause the implicit creation of a body element.
182     return !!m_bodyElement;
183 }
184
185 void HTMLElementStack::popHTMLHeadElement()
186 {
187     ASSERT(top() == m_headElement);
188     m_headElement = 0;
189     popCommon();
190 }
191
192 void HTMLElementStack::popHTMLBodyElement()
193 {
194     ASSERT(top() == m_bodyElement);
195     m_bodyElement = 0;
196     popCommon();
197 }
198
199 void HTMLElementStack::popAll()
200 {
201     m_rootNode = 0;
202     m_headElement = 0;
203     m_bodyElement = 0;
204     m_stackDepth = 0;
205     while (m_top) {
206         topNode()->finishParsingChildren();
207         m_top = m_top->releaseNext();
208     }
209 }
210
211 void HTMLElementStack::pop()
212 {
213     ASSERT(!top()->hasTagName(HTMLNames::headTag));
214     popCommon();
215 }
216
217 void HTMLElementStack::popUntil(const AtomicString& tagName)
218 {
219     while (!top()->hasLocalName(tagName)) {
220         // pop() will ASSERT at <body> if callers fail to check that there is an
221         // element with localName |tagName| on the stack of open elements.
222         pop();
223     }
224 }
225
226 void HTMLElementStack::popUntilPopped(const AtomicString& tagName)
227 {
228     popUntil(tagName);
229     pop();
230 }
231
232 void HTMLElementStack::popUntilNumberedHeaderElementPopped()
233 {
234     while (!isNumberedHeaderElement(topNode()))
235         pop();
236     pop();
237 }
238
239 void HTMLElementStack::popUntil(Element* element)
240 {
241     while (top() != element)
242         pop();
243 }
244
245 void HTMLElementStack::popUntilPopped(Element* element)
246 {
247     popUntil(element);
248     pop();
249 }
250
251 void HTMLElementStack::popUntilTableScopeMarker()
252 {
253     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-context
254     while (!isTableScopeMarker(topNode()))
255         pop();
256 }
257
258 void HTMLElementStack::popUntilTableBodyScopeMarker()
259 {
260     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-body-context
261     while (!isTableBodyScopeMarker(topNode()))
262         pop();
263 }
264
265 void HTMLElementStack::popUntilTableRowScopeMarker()
266 {
267     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-row-context
268     while (!isTableRowScopeMarker(topNode()))
269         pop();
270 }
271
272 // http://www.whatwg.org/specs/web-apps/current-work/multipage/tree-construction.html#mathml-text-integration-point
273 bool HTMLElementStack::isMathMLTextIntegrationPoint(ContainerNode* node)
274 {
275     if (!node->isElementNode())
276         return false;
277     Element* element = static_cast<Element*>(node);
278     return element->hasTagName(MathMLNames::miTag)
279         || element->hasTagName(MathMLNames::moTag)
280         || element->hasTagName(MathMLNames::mnTag)
281         || element->hasTagName(MathMLNames::msTag)
282         || element->hasTagName(MathMLNames::mtextTag);
283 }
284
285 // http://www.whatwg.org/specs/web-apps/current-work/multipage/tree-construction.html#html-integration-point
286 bool HTMLElementStack::isHTMLIntegrationPoint(ContainerNode* node)
287 {
288     if (!node->isElementNode())
289         return false;
290     Element* element = static_cast<Element*>(node);
291     if (element->hasTagName(MathMLNames::annotation_xmlTag)) {
292         // FIXME: Technically we shouldn't read back from the DOM here.
293         // Instead, we're supposed to track this information in the element
294         // stack, which lets the parser run on its own thread.
295         String encoding = element->fastGetAttribute(MathMLNames::encodingAttr);
296         return equalIgnoringCase(encoding, "text/html")
297             || equalIgnoringCase(encoding, "application/xhtml+xml");
298     }
299     return element->hasTagName(SVGNames::foreignObjectTag)
300         || element->hasTagName(SVGNames::descTag)
301         || element->hasTagName(SVGNames::titleTag);
302 }
303
304 void HTMLElementStack::popUntilForeignContentScopeMarker()
305 {
306     while (!isForeignContentScopeMarker(topNode()))
307         pop();
308 }
309     
310 void HTMLElementStack::pushRootNode(PassRefPtr<ContainerNode> rootNode)
311 {
312     ASSERT(rootNode->nodeType() == Node::DOCUMENT_FRAGMENT_NODE);
313     pushRootNodeCommon(rootNode);
314 }
315
316 void HTMLElementStack::pushHTMLHtmlElement(PassRefPtr<Element> element)
317 {
318     ASSERT(element->hasTagName(HTMLNames::htmlTag));
319     pushRootNodeCommon(element);
320 }
321     
322 void HTMLElementStack::pushRootNodeCommon(PassRefPtr<ContainerNode> rootNode)
323 {
324     ASSERT(!m_top);
325     ASSERT(!m_rootNode);
326     m_rootNode = rootNode.get();
327     pushCommon(rootNode);
328 }
329
330 void HTMLElementStack::pushHTMLHeadElement(PassRefPtr<Element> element)
331 {
332     ASSERT(element->hasTagName(HTMLNames::headTag));
333     ASSERT(!m_headElement);
334     m_headElement = element.get();
335     pushCommon(element);
336 }
337
338 void HTMLElementStack::pushHTMLBodyElement(PassRefPtr<Element> element)
339 {
340     ASSERT(element->hasTagName(HTMLNames::bodyTag));
341     ASSERT(!m_bodyElement);
342     m_bodyElement = element.get();
343     pushCommon(element);
344 }
345
346 void HTMLElementStack::push(PassRefPtr<Element> element)
347 {
348     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
349     ASSERT(!element->hasTagName(HTMLNames::headTag));
350     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
351     ASSERT(m_rootNode);
352     pushCommon(element);
353 }
354
355 void HTMLElementStack::insertAbove(PassRefPtr<Element> element, ElementRecord* recordBelow)
356 {
357     ASSERT(element);
358     ASSERT(recordBelow);
359     ASSERT(m_top);
360     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
361     ASSERT(!element->hasTagName(HTMLNames::headTag));
362     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
363     ASSERT(m_rootNode);
364     if (recordBelow == m_top) {
365         push(element);
366         return;
367     }
368
369     for (ElementRecord* recordAbove = m_top.get(); recordAbove; recordAbove = recordAbove->next()) {
370         if (recordAbove->next() != recordBelow)
371             continue;
372
373         m_stackDepth++;
374         recordAbove->setNext(adoptPtr(new ElementRecord(element, recordAbove->releaseNext())));
375         recordAbove->next()->element()->beginParsingChildren();
376         return;
377     }
378     ASSERT_NOT_REACHED();
379 }
380
381 HTMLElementStack::ElementRecord* HTMLElementStack::topRecord() const
382 {
383     ASSERT(m_top);
384     return m_top.get();
385 }
386
387 Element* HTMLElementStack::oneBelowTop() const
388 {
389     // We should never be calling this if it could be 0.
390     ASSERT(m_top);
391     ASSERT(m_top->next());
392     return m_top->next()->element();
393 }
394
395 Element* HTMLElementStack::bottom() const
396 {
397     return htmlElement();
398 }
399
400 void HTMLElementStack::removeHTMLHeadElement(Element* element)
401 {
402     ASSERT(m_headElement == element);
403     if (m_top->element() == element) {
404         popHTMLHeadElement();
405         return;
406     }
407     m_headElement = 0;
408     removeNonTopCommon(element);
409 }
410
411 void HTMLElementStack::remove(Element* element)
412 {
413     ASSERT(!element->hasTagName(HTMLNames::headTag));
414     if (m_top->element() == element) {
415         pop();
416         return;
417     }
418     removeNonTopCommon(element);
419 }
420
421 HTMLElementStack::ElementRecord* HTMLElementStack::find(Element* element) const
422 {
423     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
424         if (pos->node() == element)
425             return pos;
426     }
427     return 0;
428 }
429
430 HTMLElementStack::ElementRecord* HTMLElementStack::topmost(const AtomicString& tagName) const
431 {
432     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
433         if (pos->node()->hasLocalName(tagName))
434             return pos;
435     }
436     return 0;
437 }
438
439 bool HTMLElementStack::contains(Element* element) const
440 {
441     return !!find(element);
442 }
443
444 bool HTMLElementStack::contains(const AtomicString& tagName) const
445 {
446     return !!topmost(tagName);
447 }
448
449 template <bool isMarker(ContainerNode*)>
450 bool inScopeCommon(HTMLElementStack::ElementRecord* top, const AtomicString& targetTag)
451 {
452     for (HTMLElementStack::ElementRecord* pos = top; pos; pos = pos->next()) {
453         ContainerNode* node = pos->node();
454         if (node->hasLocalName(targetTag))
455             return true;
456         if (isMarker(node))
457             return false;
458     }
459     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
460     return false;
461 }
462
463 bool HTMLElementStack::hasOnlyHTMLElementsInScope() const
464 {
465     for (ElementRecord* record = m_top.get(); record; record = record->next()) {
466         ContainerNode* node = record->node();
467         if (!isInHTMLNamespace(node))
468             return false;
469         if (isScopeMarker(node))
470             return true;
471     }
472     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
473     return true;
474 }
475
476 bool HTMLElementStack::hasNumberedHeaderElementInScope() const
477 {
478     for (ElementRecord* record = m_top.get(); record; record = record->next()) {
479         ContainerNode* node = record->node();
480         if (isNumberedHeaderElement(node))
481             return true;
482         if (isScopeMarker(node))
483             return false;
484     }
485     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
486     return false;
487 }
488
489 bool HTMLElementStack::inScope(Element* targetElement) const
490 {
491     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
492         ContainerNode* node = pos->node();
493         if (node == targetElement)
494             return true;
495         if (isScopeMarker(node))
496             return false;
497     }
498     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
499     return false;
500 }
501
502 bool HTMLElementStack::inScope(const AtomicString& targetTag) const
503 {
504     return inScopeCommon<isScopeMarker>(m_top.get(), targetTag);
505 }
506
507 bool HTMLElementStack::inScope(const QualifiedName& tagName) const
508 {
509     // FIXME: Is localName() right for non-html elements?
510     return inScope(tagName.localName());
511 }
512
513 bool HTMLElementStack::inListItemScope(const AtomicString& targetTag) const
514 {
515     return inScopeCommon<isListItemScopeMarker>(m_top.get(), targetTag);
516 }
517
518 bool HTMLElementStack::inListItemScope(const QualifiedName& tagName) const
519 {
520     // FIXME: Is localName() right for non-html elements?
521     return inListItemScope(tagName.localName());
522 }
523
524 bool HTMLElementStack::inTableScope(const AtomicString& targetTag) const
525 {
526     return inScopeCommon<isTableScopeMarker>(m_top.get(), targetTag);
527 }
528
529 bool HTMLElementStack::inTableScope(const QualifiedName& tagName) const
530 {
531     // FIXME: Is localName() right for non-html elements?
532     return inTableScope(tagName.localName());
533 }
534
535 bool HTMLElementStack::inButtonScope(const AtomicString& targetTag) const
536 {
537     return inScopeCommon<isButtonScopeMarker>(m_top.get(), targetTag);
538 }
539
540 bool HTMLElementStack::inButtonScope(const QualifiedName& tagName) const
541 {
542     // FIXME: Is localName() right for non-html elements?
543     return inButtonScope(tagName.localName());
544 }
545
546 bool HTMLElementStack::inSelectScope(const AtomicString& targetTag) const
547 {
548     return inScopeCommon<isSelectScopeMarker>(m_top.get(), targetTag);
549 }
550
551 bool HTMLElementStack::inSelectScope(const QualifiedName& tagName) const
552 {
553     // FIXME: Is localName() right for non-html elements?
554     return inSelectScope(tagName.localName());
555 }
556
557 Element* HTMLElementStack::htmlElement() const
558 {
559     ASSERT(m_rootNode);
560     return toElement(m_rootNode);
561 }
562
563 Element* HTMLElementStack::headElement() const
564 {
565     ASSERT(m_headElement);
566     return m_headElement;
567 }
568
569 Element* HTMLElementStack::bodyElement() const
570 {
571     ASSERT(m_bodyElement);
572     return m_bodyElement;
573 }
574     
575 ContainerNode* HTMLElementStack::rootNode() const
576 {
577     ASSERT(m_rootNode);
578     return m_rootNode;
579 }
580
581 void HTMLElementStack::pushCommon(PassRefPtr<ContainerNode> node)
582 {
583     ASSERT(m_rootNode);
584
585     m_stackDepth++;
586     m_top = adoptPtr(new ElementRecord(node, m_top.release()));
587 }
588
589 void HTMLElementStack::popCommon()
590 {
591     ASSERT(!top()->hasTagName(HTMLNames::htmlTag));
592     ASSERT(!top()->hasTagName(HTMLNames::headTag) || !m_headElement);
593     ASSERT(!top()->hasTagName(HTMLNames::bodyTag) || !m_bodyElement);
594     top()->finishParsingChildren();
595     m_top = m_top->releaseNext();
596
597     m_stackDepth--;
598 }
599
600 void HTMLElementStack::removeNonTopCommon(Element* element)
601 {
602     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
603     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
604     ASSERT(top() != element);
605     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
606         if (pos->next()->element() == element) {
607             // FIXME: Is it OK to call finishParsingChildren()
608             // when the children aren't actually finished?
609             element->finishParsingChildren();
610             pos->setNext(pos->next()->releaseNext());
611             m_stackDepth--;
612             return;
613         }
614     }
615     ASSERT_NOT_REACHED();
616 }
617
618 #ifndef NDEBUG
619
620 void HTMLElementStack::show()
621 {
622     for (ElementRecord* record = m_top.get(); record; record = record->next())
623         record->element()->showNode();
624 }
625
626 #endif
627
628 }