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