Rename AtomicString to AtomString
[WebKit-https.git] / 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 "HTMLOptGroupElement.h"
32 #include "HTMLOptionElement.h"
33 #include "HTMLTableElement.h"
34
35 namespace WebCore {
36
37 using namespace HTMLNames;
38
39 namespace {
40
41 inline bool isRootNode(HTMLStackItem& item)
42 {
43     return item.isDocumentFragment() || item.hasTagName(htmlTag);
44 }
45
46 inline 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
68 inline bool isListItemScopeMarker(HTMLStackItem& item)
69 {
70     return isScopeMarker(item)
71         || item.hasTagName(olTag)
72         || item.hasTagName(ulTag);
73 }
74
75 inline bool isTableScopeMarker(HTMLStackItem& item)
76 {
77     return is<HTMLTableElement>(item.node())
78         || item.hasTagName(templateTag)
79         || isRootNode(item);
80 }
81
82 inline 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
91 inline bool isTableRowScopeMarker(HTMLStackItem& item)
92 {
93     return item.hasTagName(trTag)
94         || item.hasTagName(templateTag)
95         || isRootNode(item);
96 }
97
98 inline bool isForeignContentScopeMarker(HTMLStackItem& item)
99 {
100     return HTMLElementStack::isMathMLTextIntegrationPoint(item)
101         || HTMLElementStack::isHTMLIntegrationPoint(item)
102         || isInHTMLNamespace(item);
103 }
104
105 inline bool isButtonScopeMarker(HTMLStackItem& item)
106 {
107     return isScopeMarker(item)
108         || item.hasTagName(buttonTag);
109 }
110
111 inline bool isSelectScopeMarker(HTMLStackItem& item)
112 {
113     return !is<HTMLOptGroupElement>(item.node()) && !is<HTMLOptionElement>(item.node());
114 }
115
116 }
117
118 HTMLElementStack::ElementRecord::ElementRecord(Ref<HTMLStackItem>&& item, std::unique_ptr<ElementRecord> next)
119     : m_item(WTFMove(item))
120     , m_next(WTFMove(next))
121 {
122 }
123
124 HTMLElementStack::ElementRecord::~ElementRecord() = default;
125
126 void 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
133 bool 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
142 HTMLElementStack::~HTMLElementStack() = default;
143
144 bool HTMLElementStack::hasOnlyOneElement() const
145 {
146     return !topRecord().next();
147 }
148
149 bool 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
161 void HTMLElementStack::popHTMLHeadElement()
162 {
163     ASSERT(&top() == m_headElement);
164     m_headElement = nullptr;
165     popCommon();
166 }
167
168 void HTMLElementStack::popHTMLBodyElement()
169 {
170     ASSERT(&top() == m_bodyElement);
171     m_bodyElement = nullptr;
172     popCommon();
173 }
174
175 void 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
187 void HTMLElementStack::pop()
188 {
189     ASSERT(!topStackItem().hasTagName(HTMLNames::headTag));
190     popCommon();
191 }
192
193 void HTMLElementStack::popUntil(const AtomString& 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
201 void HTMLElementStack::popUntilPopped(const AtomString& tagName)
202 {
203     popUntil(tagName);
204     pop();
205 }
206
207 void HTMLElementStack::popUntilNumberedHeaderElementPopped()
208 {
209     while (!isNumberedHeaderElement(topStackItem()))
210         pop();
211     pop();
212 }
213
214 void HTMLElementStack::popUntil(Element& element)
215 {
216     while (&top() != &element)
217         pop();
218 }
219
220 void HTMLElementStack::popUntilPopped(Element& element)
221 {
222     popUntil(element);
223     pop();
224 }
225
226 void 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
233 void 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
240 void 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
248 bool 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
258 bool 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
274 void HTMLElementStack::popUntilForeignContentScopeMarker()
275 {
276     while (!isForeignContentScopeMarker(topStackItem()))
277         pop();
278 }
279     
280 void HTMLElementStack::pushRootNode(Ref<HTMLStackItem>&& rootItem)
281 {
282     ASSERT(rootItem->isDocumentFragment());
283     pushRootNodeCommon(WTFMove(rootItem));
284 }
285
286 void HTMLElementStack::pushHTMLHtmlElement(Ref<HTMLStackItem>&& item)
287 {
288     ASSERT(item->hasTagName(HTMLNames::htmlTag));
289     pushRootNodeCommon(WTFMove(item));
290 }
291     
292 void 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
300 void 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
308 void 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
316 void 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
325 void 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
349 auto HTMLElementStack::topRecord() const -> ElementRecord&
350 {
351     ASSERT(m_top);
352     return *m_top;
353 }
354
355 HTMLStackItem* 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
365 void 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
376 void 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
386 auto 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
395 auto HTMLElementStack::topmost(const AtomString& 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
404 bool HTMLElementStack::contains(Element& element) const
405 {
406     return !!find(element);
407 }
408
409 bool HTMLElementStack::contains(const AtomString& tagName) const
410 {
411     return !!topmost(tagName);
412 }
413
414 template <bool isMarker(HTMLStackItem&)> bool inScopeCommon(HTMLElementStack::ElementRecord* top, const AtomString& 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
427 bool 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
440 bool 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
453 bool HTMLElementStack::inScope(const AtomString& targetTag) const
454 {
455     return inScopeCommon<isScopeMarker>(m_top.get(), targetTag);
456 }
457
458 bool HTMLElementStack::inScope(const QualifiedName& tagName) const
459 {
460     return inScope(tagName.localName());
461 }
462
463 bool HTMLElementStack::inListItemScope(const AtomString& targetTag) const
464 {
465     return inScopeCommon<isListItemScopeMarker>(m_top.get(), targetTag);
466 }
467
468 bool HTMLElementStack::inListItemScope(const QualifiedName& tagName) const
469 {
470     return inListItemScope(tagName.localName());
471 }
472
473 bool HTMLElementStack::inTableScope(const AtomString& targetTag) const
474 {
475     return inScopeCommon<isTableScopeMarker>(m_top.get(), targetTag);
476 }
477
478 bool HTMLElementStack::inTableScope(const QualifiedName& tagName) const
479 {
480     return inTableScope(tagName.localName());
481 }
482
483 bool HTMLElementStack::inButtonScope(const AtomString& targetTag) const
484 {
485     return inScopeCommon<isButtonScopeMarker>(m_top.get(), targetTag);
486 }
487
488 bool HTMLElementStack::inButtonScope(const QualifiedName& tagName) const
489 {
490     return inButtonScope(tagName.localName());
491 }
492
493 bool HTMLElementStack::inSelectScope(const AtomString& targetTag) const
494 {
495     return inScopeCommon<isSelectScopeMarker>(m_top.get(), targetTag);
496 }
497
498 bool HTMLElementStack::inSelectScope(const QualifiedName& tagName) const
499 {
500     return inSelectScope(tagName.localName());
501 }
502
503 bool HTMLElementStack::hasTemplateInHTMLScope() const
504 {
505     return inScopeCommon<isRootNode>(m_top.get(), templateTag->localName());
506 }
507
508 Element& HTMLElementStack::htmlElement() const
509 {
510     return downcast<Element>(rootNode());
511 }
512
513 Element& HTMLElementStack::headElement() const
514 {
515     ASSERT(m_headElement);
516     return *m_headElement;
517 }
518
519 Element& HTMLElementStack::bodyElement() const
520 {
521     ASSERT(m_bodyElement);
522     return *m_bodyElement;
523 }
524     
525 ContainerNode& HTMLElementStack::rootNode() const
526 {
527     ASSERT(m_rootNode);
528     return *m_rootNode;
529 }
530
531 void 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
539 void 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
551 void 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
569 auto 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
584 void HTMLElementStack::show()
585 {
586     for (auto* record = m_top.get(); record; record = record->next())
587         record->element().showNode();
588 }
589
590 #endif
591
592 }