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