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