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