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