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