397d1e6ec0b2ee5c3e0a013f3d254ff844daa8ad
[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
40 namespace {
41
42 inline bool isRootNode(HTMLStackItem* item)
43 {
44     return item->isDocumentFragmentNode()
45         || item->hasTagName(htmlTag);
46 }
47
48 inline bool isScopeMarker(HTMLStackItem* item)
49 {
50     return item->hasTagName(appletTag)
51         || item->hasTagName(captionTag)
52         || item->hasTagName(marqueeTag)
53         || item->hasTagName(objectTag)
54         || is<HTMLTableElement>(*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
72 inline bool isListItemScopeMarker(HTMLStackItem* item)
73 {
74     return isScopeMarker(item)
75         || item->hasTagName(olTag)
76         || item->hasTagName(ulTag);
77 }
78
79 inline bool isTableScopeMarker(HTMLStackItem* item)
80 {
81     return is<HTMLTableElement>(*item->node())
82 #if ENABLE(TEMPLATE_ELEMENT)
83         || item->hasTagName(templateTag)
84 #endif
85         || isRootNode(item);
86 }
87
88 inline 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
99 inline 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
108 inline bool isForeignContentScopeMarker(HTMLStackItem* item)
109 {
110     return HTMLElementStack::isMathMLTextIntegrationPoint(item)
111         || HTMLElementStack::isHTMLIntegrationPoint(item)
112         || item->isInHTMLNamespace();
113 }
114
115 inline bool isButtonScopeMarker(HTMLStackItem* item)
116 {
117     return isScopeMarker(item)
118         || item->hasTagName(buttonTag);
119 }
120
121 inline bool isSelectScopeMarker(HTMLStackItem* item)
122 {
123     return !is<HTMLOptGroupElement>(*item->node()) && !is<HTMLOptionElement>(*item->node());
124 }
125
126 }
127
128 HTMLElementStack::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
135 HTMLElementStack::ElementRecord::~ElementRecord()
136 {
137 }
138
139 void 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
147 bool 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
156 HTMLElementStack::HTMLElementStack()
157     : m_rootNode(0)
158     , m_headElement(0)
159     , m_bodyElement(0)
160     , m_stackDepth(0)
161 {
162 }
163
164 HTMLElementStack::~HTMLElementStack()
165 {
166 }
167
168 bool HTMLElementStack::hasOnlyOneElement() const
169 {
170     return !topRecord()->next();
171 }
172
173 bool 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
185 void HTMLElementStack::popHTMLHeadElement()
186 {
187     ASSERT(top() == m_headElement);
188     m_headElement = 0;
189     popCommon();
190 }
191
192 void HTMLElementStack::popHTMLBodyElement()
193 {
194     ASSERT(top() == m_bodyElement);
195     m_bodyElement = 0;
196     popCommon();
197 }
198
199 void 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
211 void HTMLElementStack::pop()
212 {
213     ASSERT(!topStackItem()->hasTagName(HTMLNames::headTag));
214     popCommon();
215 }
216
217 void 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
225 void HTMLElementStack::popUntilPopped(const AtomicString& tagName)
226 {
227     popUntil(tagName);
228     pop();
229 }
230
231 void HTMLElementStack::popUntilNumberedHeaderElementPopped()
232 {
233     while (!topStackItem()->isNumberedHeaderElement())
234         pop();
235     pop();
236 }
237
238 void HTMLElementStack::popUntil(Element* element)
239 {
240     while (top() != element)
241         pop();
242 }
243
244 void HTMLElementStack::popUntilPopped(Element* element)
245 {
246     popUntil(element);
247     pop();
248 }
249
250 void 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
257 void 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
264 void 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
272 bool 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
284 bool 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
302 void HTMLElementStack::popUntilForeignContentScopeMarker()
303 {
304     while (!isForeignContentScopeMarker(topStackItem()))
305         pop();
306 }
307     
308 void HTMLElementStack::pushRootNode(PassRefPtr<HTMLStackItem> rootItem)
309 {
310     ASSERT(rootItem->isDocumentFragmentNode());
311     pushRootNodeCommon(rootItem);
312 }
313
314 void HTMLElementStack::pushHTMLHtmlElement(PassRefPtr<HTMLStackItem> item)
315 {
316     ASSERT(item->hasTagName(HTMLNames::htmlTag));
317     pushRootNodeCommon(item);
318 }
319     
320 void HTMLElementStack::pushRootNodeCommon(PassRefPtr<HTMLStackItem> rootItem)
321 {
322     ASSERT(!m_top);
323     ASSERT(!m_rootNode);
324     m_rootNode = rootItem->node();
325     pushCommon(rootItem);
326 }
327
328 void 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
336 void 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
344 void 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
353 void 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
379 HTMLElementStack::ElementRecord* HTMLElementStack::topRecord() const
380 {
381     ASSERT(m_top);
382     return m_top.get();
383 }
384
385 HTMLStackItem* 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
395 void 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
406 void 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
416 HTMLElementStack::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
425 HTMLElementStack::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
434 bool HTMLElementStack::contains(Element* element) const
435 {
436     return !!find(element);
437 }
438
439 bool HTMLElementStack::contains(const AtomicString& tagName) const
440 {
441     return !!topmost(tagName);
442 }
443
444 template <bool isMarker(HTMLStackItem*)>
445 bool 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
458 bool 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
471 bool 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
484 bool HTMLElementStack::inScope(const AtomicString& targetTag) const
485 {
486     return inScopeCommon<isScopeMarker>(m_top.get(), targetTag);
487 }
488
489 bool HTMLElementStack::inScope(const QualifiedName& tagName) const
490 {
491     return inScope(tagName.localName());
492 }
493
494 bool HTMLElementStack::inListItemScope(const AtomicString& targetTag) const
495 {
496     return inScopeCommon<isListItemScopeMarker>(m_top.get(), targetTag);
497 }
498
499 bool HTMLElementStack::inListItemScope(const QualifiedName& tagName) const
500 {
501     return inListItemScope(tagName.localName());
502 }
503
504 bool HTMLElementStack::inTableScope(const AtomicString& targetTag) const
505 {
506     return inScopeCommon<isTableScopeMarker>(m_top.get(), targetTag);
507 }
508
509 bool HTMLElementStack::inTableScope(const QualifiedName& tagName) const
510 {
511     return inTableScope(tagName.localName());
512 }
513
514 bool HTMLElementStack::inButtonScope(const AtomicString& targetTag) const
515 {
516     return inScopeCommon<isButtonScopeMarker>(m_top.get(), targetTag);
517 }
518
519 bool HTMLElementStack::inButtonScope(const QualifiedName& tagName) const
520 {
521     return inButtonScope(tagName.localName());
522 }
523
524 bool HTMLElementStack::inSelectScope(const AtomicString& targetTag) const
525 {
526     return inScopeCommon<isSelectScopeMarker>(m_top.get(), targetTag);
527 }
528
529 bool HTMLElementStack::inSelectScope(const QualifiedName& tagName) const
530 {
531     return inSelectScope(tagName.localName());
532 }
533
534 #if ENABLE(TEMPLATE_ELEMENT)
535 bool HTMLElementStack::hasTemplateInHTMLScope() const
536 {
537     return inScopeCommon<isRootNode>(m_top.get(), templateTag.localName());
538 }
539 #endif
540
541 Element* HTMLElementStack::htmlElement() const
542 {
543     ASSERT(m_rootNode);
544     return downcast<Element>(m_rootNode);
545 }
546
547 Element* HTMLElementStack::headElement() const
548 {
549     ASSERT(m_headElement);
550     return m_headElement;
551 }
552
553 Element* HTMLElementStack::bodyElement() const
554 {
555     ASSERT(m_bodyElement);
556     return m_bodyElement;
557 }
558     
559 ContainerNode* HTMLElementStack::rootNode() const
560 {
561     ASSERT(m_rootNode);
562     return m_rootNode;
563 }
564
565 void 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
573 void 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
584 void 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
602 HTMLElementStack::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
617 void HTMLElementStack::show()
618 {
619     for (ElementRecord* record = m_top.get(); record; record = record->next())
620         record->element()->showNode();
621 }
622
623 #endif
624
625 }