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