src/third_party/WebKit/Source/core/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 "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 blink {
  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 nullptr;
 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 nullptr;
 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 nullptr;
 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 nullptr;
 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 }