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