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