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