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