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