Use the original token to create an element in "reconstruct the active formatting...
[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 "Element.h"
32 #include "HTMLNames.h"
33 #include "MathMLNames.h"
34 #include "SVGNames.h"
35 #include <wtf/PassOwnPtr.h>
36
37 namespace WebCore {
38
39 using namespace HTMLNames;
40
41 namespace {
42
43 inline bool isNumberedHeaderElement(ContainerNode* node)
44 {
45     return node->hasTagName(h1Tag)
46         || node->hasTagName(h2Tag)
47         || node->hasTagName(h3Tag)
48         || node->hasTagName(h4Tag)
49         || node->hasTagName(h5Tag)
50         || node->hasTagName(h6Tag);
51 }
52     
53 inline bool isRootNode(ContainerNode* node)
54 {
55     return node->nodeType() == Node::DOCUMENT_FRAGMENT_NODE
56         || node->hasTagName(htmlTag);
57 }
58
59 inline bool isScopeMarker(ContainerNode* node)
60 {
61     return node->hasTagName(appletTag)
62         || node->hasTagName(captionTag)
63         || node->hasTagName(marqueeTag)
64         || node->hasTagName(objectTag)
65         || node->hasTagName(tableTag)
66         || node->hasTagName(tdTag)
67         || node->hasTagName(thTag)
68         || node->hasTagName(MathMLNames::miTag)
69         || node->hasTagName(MathMLNames::moTag)
70         || node->hasTagName(MathMLNames::mnTag)
71         || node->hasTagName(MathMLNames::msTag)
72         || node->hasTagName(MathMLNames::mtextTag)
73         || node->hasTagName(MathMLNames::annotation_xmlTag)
74         || node->hasTagName(SVGNames::foreignObjectTag)
75         || node->hasTagName(SVGNames::descTag)
76         || node->hasTagName(SVGNames::titleTag)
77         || isRootNode(node);
78 }
79
80 inline bool isListItemScopeMarker(ContainerNode* node)
81 {
82     return isScopeMarker(node)
83         || node->hasTagName(olTag)
84         || node->hasTagName(ulTag);
85 }
86
87 inline bool isTableScopeMarker(ContainerNode* node)
88 {
89     return node->hasTagName(tableTag)
90         || isRootNode(node);
91 }
92
93 inline bool isTableBodyScopeMarker(ContainerNode* node)
94 {
95     return node->hasTagName(tbodyTag)
96         || node->hasTagName(tfootTag)
97         || node->hasTagName(theadTag)
98         || isRootNode(node);
99 }
100
101 inline bool isTableRowScopeMarker(ContainerNode* node)
102 {
103     return node->hasTagName(trTag)
104         || isRootNode(node);
105 }
106
107 inline bool isForeignContentScopeMarker(ContainerNode* node)
108 {
109     return HTMLElementStack::isMathMLTextIntegrationPoint(node)
110         || HTMLElementStack::isHTMLIntegrationPoint(node)
111         || isInHTMLNamespace(node);
112 }
113
114 inline bool isButtonScopeMarker(ContainerNode* node)
115 {
116     return isScopeMarker(node)
117         || node->hasTagName(buttonTag);
118 }
119
120 inline bool isSelectScopeMarker(ContainerNode* node)
121 {
122     return !node->hasTagName(optgroupTag)
123         && !node->hasTagName(optionTag);
124 }
125
126 }
127
128 HTMLElementStack::ElementRecord::ElementRecord(PassRefPtr<HTMLStackItem> item, PassOwnPtr<ElementRecord> next)
129     : m_item(item)
130     , m_next(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->node()->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(!top()->hasTagName(HTMLNames::headTag));
214     popCommon();
215 }
216
217 void HTMLElementStack::popUntil(const AtomicString& tagName)
218 {
219     while (!top()->hasLocalName(tagName)) {
220         // pop() will ASSERT at <body> if callers fail to check that there is an
221         // element with localName |tagName| on the stack of open elements.
222         pop();
223     }
224 }
225
226 void HTMLElementStack::popUntilPopped(const AtomicString& tagName)
227 {
228     popUntil(tagName);
229     pop();
230 }
231
232 void HTMLElementStack::popUntilNumberedHeaderElementPopped()
233 {
234     while (!isNumberedHeaderElement(topNode()))
235         pop();
236     pop();
237 }
238
239 void HTMLElementStack::popUntil(Element* element)
240 {
241     while (top() != element)
242         pop();
243 }
244
245 void HTMLElementStack::popUntilPopped(Element* element)
246 {
247     popUntil(element);
248     pop();
249 }
250
251 void HTMLElementStack::popUntilTableScopeMarker()
252 {
253     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-context
254     while (!isTableScopeMarker(topNode()))
255         pop();
256 }
257
258 void HTMLElementStack::popUntilTableBodyScopeMarker()
259 {
260     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-body-context
261     while (!isTableBodyScopeMarker(topNode()))
262         pop();
263 }
264
265 void HTMLElementStack::popUntilTableRowScopeMarker()
266 {
267     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-row-context
268     while (!isTableRowScopeMarker(topNode()))
269         pop();
270 }
271
272 // http://www.whatwg.org/specs/web-apps/current-work/multipage/tree-construction.html#mathml-text-integration-point
273 bool HTMLElementStack::isMathMLTextIntegrationPoint(ContainerNode* node)
274 {
275     if (!node->isElementNode())
276         return false;
277     Element* element = static_cast<Element*>(node);
278     return element->hasTagName(MathMLNames::miTag)
279         || element->hasTagName(MathMLNames::moTag)
280         || element->hasTagName(MathMLNames::mnTag)
281         || element->hasTagName(MathMLNames::msTag)
282         || element->hasTagName(MathMLNames::mtextTag);
283 }
284
285 // http://www.whatwg.org/specs/web-apps/current-work/multipage/tree-construction.html#html-integration-point
286 bool HTMLElementStack::isHTMLIntegrationPoint(ContainerNode* node)
287 {
288     if (!node->isElementNode())
289         return false;
290     Element* element = static_cast<Element*>(node);
291     if (element->hasTagName(MathMLNames::annotation_xmlTag)) {
292         // FIXME: Technically we shouldn't read back from the DOM here.
293         // Instead, we're supposed to track this information in the element
294         // stack, which lets the parser run on its own thread.
295         String encoding = element->fastGetAttribute(MathMLNames::encodingAttr);
296         return equalIgnoringCase(encoding, "text/html")
297             || equalIgnoringCase(encoding, "application/xhtml+xml");
298     }
299     return element->hasTagName(SVGNames::foreignObjectTag)
300         || element->hasTagName(SVGNames::descTag)
301         || element->hasTagName(SVGNames::titleTag);
302 }
303
304 void HTMLElementStack::popUntilForeignContentScopeMarker()
305 {
306     while (!isForeignContentScopeMarker(topNode()))
307         pop();
308 }
309     
310 void HTMLElementStack::pushRootNode(PassRefPtr<HTMLStackItem> rootItem)
311 {
312     ASSERT(rootItem->node()->nodeType() == Node::DOCUMENT_FRAGMENT_NODE);
313     pushRootNodeCommon(rootItem);
314 }
315
316 void HTMLElementStack::pushHTMLHtmlElement(PassRefPtr<HTMLStackItem> item)
317 {
318     ASSERT(item->element()->hasTagName(HTMLNames::htmlTag));
319     pushRootNodeCommon(item);
320 }
321     
322 void HTMLElementStack::pushRootNodeCommon(PassRefPtr<HTMLStackItem> rootItem)
323 {
324     ASSERT(!m_top);
325     ASSERT(!m_rootNode);
326     m_rootNode = rootItem->node();
327     pushCommon(rootItem);
328 }
329
330 void HTMLElementStack::pushHTMLHeadElement(PassRefPtr<HTMLStackItem> item)
331 {
332     ASSERT(item->element()->hasTagName(HTMLNames::headTag));
333     ASSERT(!m_headElement);
334     m_headElement = item->element();
335     pushCommon(item);
336 }
337
338 void HTMLElementStack::pushHTMLBodyElement(PassRefPtr<HTMLStackItem> item)
339 {
340     ASSERT(item->element()->hasTagName(HTMLNames::bodyTag));
341     ASSERT(!m_bodyElement);
342     m_bodyElement = item->element();
343     pushCommon(item);
344 }
345
346 void HTMLElementStack::push(PassRefPtr<HTMLStackItem> item)
347 {
348     ASSERT(!item->element()->hasTagName(HTMLNames::htmlTag));
349     ASSERT(!item->element()->hasTagName(HTMLNames::headTag));
350     ASSERT(!item->element()->hasTagName(HTMLNames::bodyTag));
351     ASSERT(m_rootNode);
352     pushCommon(item);
353 }
354
355 void HTMLElementStack::insertAbove(PassRefPtr<HTMLStackItem> item, ElementRecord* recordBelow)
356 {
357     ASSERT(item);
358     ASSERT(recordBelow);
359     ASSERT(m_top);
360     ASSERT(!item->element()->hasTagName(HTMLNames::htmlTag));
361     ASSERT(!item->element()->hasTagName(HTMLNames::headTag));
362     ASSERT(!item->element()->hasTagName(HTMLNames::bodyTag));
363     ASSERT(m_rootNode);
364     if (recordBelow == m_top) {
365         push(item);
366         return;
367     }
368
369     for (ElementRecord* recordAbove = m_top.get(); recordAbove; recordAbove = recordAbove->next()) {
370         if (recordAbove->next() != recordBelow)
371             continue;
372
373         m_stackDepth++;
374         recordAbove->setNext(adoptPtr(new ElementRecord(item, recordAbove->releaseNext())));
375         recordAbove->next()->element()->beginParsingChildren();
376         return;
377     }
378     ASSERT_NOT_REACHED();
379 }
380
381 HTMLElementStack::ElementRecord* HTMLElementStack::topRecord() const
382 {
383     ASSERT(m_top);
384     return m_top.get();
385 }
386
387 Element* HTMLElementStack::oneBelowTop() const
388 {
389     // We should never call this if there are fewer than 2 elements on the stack.
390     ASSERT(m_top);
391     ASSERT(m_top->next());
392     if (m_top->next()->node()->isElementNode())
393         return m_top->next()->element();
394     return 0;
395 }
396
397 Element* HTMLElementStack::bottom() const
398 {
399     return htmlElement();
400 }
401
402 void HTMLElementStack::removeHTMLHeadElement(Element* element)
403 {
404     ASSERT(m_headElement == element);
405     if (m_top->element() == element) {
406         popHTMLHeadElement();
407         return;
408     }
409     m_headElement = 0;
410     removeNonTopCommon(element);
411 }
412
413 void HTMLElementStack::remove(Element* element)
414 {
415     ASSERT(!element->hasTagName(HTMLNames::headTag));
416     if (m_top->element() == element) {
417         pop();
418         return;
419     }
420     removeNonTopCommon(element);
421 }
422
423 HTMLElementStack::ElementRecord* HTMLElementStack::find(Element* element) const
424 {
425     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
426         if (pos->node() == element)
427             return pos;
428     }
429     return 0;
430 }
431
432 HTMLElementStack::ElementRecord* HTMLElementStack::topmost(const AtomicString& tagName) const
433 {
434     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
435         if (pos->node()->hasLocalName(tagName))
436             return pos;
437     }
438     return 0;
439 }
440
441 bool HTMLElementStack::contains(Element* element) const
442 {
443     return !!find(element);
444 }
445
446 bool HTMLElementStack::contains(const AtomicString& tagName) const
447 {
448     return !!topmost(tagName);
449 }
450
451 template <bool isMarker(ContainerNode*)>
452 bool inScopeCommon(HTMLElementStack::ElementRecord* top, const AtomicString& targetTag)
453 {
454     for (HTMLElementStack::ElementRecord* pos = top; pos; pos = pos->next()) {
455         ContainerNode* node = pos->node();
456         if (node->hasLocalName(targetTag))
457             return true;
458         if (isMarker(node))
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::hasNumberedHeaderElementInScope() const
466 {
467     for (ElementRecord* record = m_top.get(); record; record = record->next()) {
468         ContainerNode* node = record->node();
469         if (isNumberedHeaderElement(node))
470             return true;
471         if (isScopeMarker(node))
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(Element* targetElement) const
479 {
480     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
481         ContainerNode* node = pos->node();
482         if (node == targetElement)
483             return true;
484         if (isScopeMarker(node))
485             return false;
486     }
487     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
488     return false;
489 }
490
491 bool HTMLElementStack::inScope(const AtomicString& targetTag) const
492 {
493     return inScopeCommon<isScopeMarker>(m_top.get(), targetTag);
494 }
495
496 bool HTMLElementStack::inScope(const QualifiedName& tagName) const
497 {
498     // FIXME: Is localName() right for non-html elements?
499     return inScope(tagName.localName());
500 }
501
502 bool HTMLElementStack::inListItemScope(const AtomicString& targetTag) const
503 {
504     return inScopeCommon<isListItemScopeMarker>(m_top.get(), targetTag);
505 }
506
507 bool HTMLElementStack::inListItemScope(const QualifiedName& tagName) const
508 {
509     // FIXME: Is localName() right for non-html elements?
510     return inListItemScope(tagName.localName());
511 }
512
513 bool HTMLElementStack::inTableScope(const AtomicString& targetTag) const
514 {
515     return inScopeCommon<isTableScopeMarker>(m_top.get(), targetTag);
516 }
517
518 bool HTMLElementStack::inTableScope(const QualifiedName& tagName) const
519 {
520     // FIXME: Is localName() right for non-html elements?
521     return inTableScope(tagName.localName());
522 }
523
524 bool HTMLElementStack::inButtonScope(const AtomicString& targetTag) const
525 {
526     return inScopeCommon<isButtonScopeMarker>(m_top.get(), targetTag);
527 }
528
529 bool HTMLElementStack::inButtonScope(const QualifiedName& tagName) const
530 {
531     // FIXME: Is localName() right for non-html elements?
532     return inButtonScope(tagName.localName());
533 }
534
535 bool HTMLElementStack::inSelectScope(const AtomicString& targetTag) const
536 {
537     return inScopeCommon<isSelectScopeMarker>(m_top.get(), targetTag);
538 }
539
540 bool HTMLElementStack::inSelectScope(const QualifiedName& tagName) const
541 {
542     // FIXME: Is localName() right for non-html elements?
543     return inSelectScope(tagName.localName());
544 }
545
546 Element* HTMLElementStack::htmlElement() const
547 {
548     ASSERT(m_rootNode);
549     return toElement(m_rootNode);
550 }
551
552 Element* HTMLElementStack::headElement() const
553 {
554     ASSERT(m_headElement);
555     return m_headElement;
556 }
557
558 Element* HTMLElementStack::bodyElement() const
559 {
560     ASSERT(m_bodyElement);
561     return m_bodyElement;
562 }
563     
564 ContainerNode* HTMLElementStack::rootNode() const
565 {
566     ASSERT(m_rootNode);
567     return m_rootNode;
568 }
569
570 void HTMLElementStack::pushCommon(PassRefPtr<HTMLStackItem> item)
571 {
572     ASSERT(m_rootNode);
573
574     m_stackDepth++;
575     m_top = adoptPtr(new ElementRecord(item, m_top.release()));
576 }
577
578 void HTMLElementStack::popCommon()
579 {
580     ASSERT(!top()->hasTagName(HTMLNames::htmlTag));
581     ASSERT(!top()->hasTagName(HTMLNames::headTag) || !m_headElement);
582     ASSERT(!top()->hasTagName(HTMLNames::bodyTag) || !m_bodyElement);
583     top()->finishParsingChildren();
584     m_top = m_top->releaseNext();
585
586     m_stackDepth--;
587 }
588
589 void HTMLElementStack::removeNonTopCommon(Element* element)
590 {
591     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
592     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
593     ASSERT(top() != element);
594     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
595         if (pos->next()->element() == element) {
596             // FIXME: Is it OK to call finishParsingChildren()
597             // when the children aren't actually finished?
598             element->finishParsingChildren();
599             pos->setNext(pos->next()->releaseNext());
600             m_stackDepth--;
601             return;
602         }
603     }
604     ASSERT_NOT_REACHED();
605 }
606
607 #ifndef NDEBUG
608
609 void HTMLElementStack::show()
610 {
611     for (ElementRecord* record = m_top.get(); record; record = record->next())
612         record->element()->showNode();
613 }
614
615 #endif
616
617 }