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