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