2011-03-02 Sheriff Bot <webkit.review.bot@gmail.com>
[WebKit-https.git] / Source / WebCore / html / parser / HTMLElementStack.cpp
1 /*
2  * Copyright (C) 2010 Google, Inc. All Rights Reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY GOOGLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL GOOGLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "HTMLElementStack.h"
28
29 #include "Element.h"
30 #include "HTMLNames.h"
31 #include "MathMLNames.h"
32 #include "SVGNames.h"
33 #include <wtf/PassOwnPtr.h>
34
35 namespace WebCore {
36
37 using namespace HTMLNames;
38
39 namespace {
40
41 inline bool isNumberedHeaderElement(Element* element)
42 {
43     return element->hasTagName(h1Tag)
44         || element->hasTagName(h2Tag)
45         || element->hasTagName(h3Tag)
46         || element->hasTagName(h4Tag)
47         || element->hasTagName(h5Tag)
48         || element->hasTagName(h6Tag);
49 }
50
51 inline bool isScopeMarker(Element* element)
52 {
53     return element->hasTagName(appletTag)
54         || element->hasTagName(captionTag)
55         || element->hasTagName(htmlTag)
56         || element->hasTagName(marqueeTag)
57         || element->hasTagName(objectTag)
58         || element->hasTagName(tableTag)
59         || element->hasTagName(tdTag)
60         || element->hasTagName(thTag)
61         || element->hasTagName(MathMLNames::miTag)
62         || element->hasTagName(MathMLNames::moTag)
63         || element->hasTagName(MathMLNames::mnTag)
64         || element->hasTagName(MathMLNames::msTag)
65         || element->hasTagName(MathMLNames::mtextTag)
66         || element->hasTagName(MathMLNames::annotation_xmlTag)
67         || element->hasTagName(SVGNames::foreignObjectTag)
68         || element->hasTagName(SVGNames::descTag)
69         || element->hasTagName(SVGNames::titleTag);
70 }
71
72 inline bool isListItemScopeMarker(Element* element)
73 {
74     return isScopeMarker(element)
75         || element->hasTagName(olTag)
76         || element->hasTagName(ulTag);
77 }
78
79 inline bool isTableScopeMarker(Element* element)
80 {
81     return element->hasTagName(tableTag)
82         || element->hasTagName(htmlTag);
83 }
84
85 inline bool isTableBodyScopeMarker(Element* element)
86 {
87     return element->hasTagName(tbodyTag)
88         || element->hasTagName(tfootTag)
89         || element->hasTagName(theadTag)
90         || element->hasTagName(htmlTag);
91 }
92
93 inline bool isTableRowScopeMarker(Element* element)
94 {
95     return element->hasTagName(trTag)
96         || element->hasTagName(htmlTag);
97 }
98
99 inline bool isForeignContentScopeMarker(Element* element)
100 {
101     return element->hasTagName(MathMLNames::miTag)
102         || element->hasTagName(MathMLNames::moTag)
103         || element->hasTagName(MathMLNames::mnTag)
104         || element->hasTagName(MathMLNames::msTag)
105         || element->hasTagName(MathMLNames::mtextTag)
106         || element->hasTagName(SVGNames::foreignObjectTag)
107         || element->hasTagName(SVGNames::descTag)
108         || element->hasTagName(SVGNames::titleTag)
109         || element->namespaceURI() == HTMLNames::xhtmlNamespaceURI;
110 }
111
112 inline bool isButtonScopeMarker(Element* element)
113 {
114     return isScopeMarker(element)
115         || element->hasTagName(buttonTag);
116 }
117
118 inline bool isSelectScopeMarker(Element* element)
119 {
120     return !element->hasTagName(optgroupTag)
121         && !element->hasTagName(optionTag);
122 }
123
124 }
125
126 HTMLElementStack::ElementRecord::ElementRecord(PassRefPtr<Element> element, PassOwnPtr<ElementRecord> next)
127     : m_element(element)
128     , m_next(next)
129 {
130     ASSERT(m_element);
131 }
132
133 HTMLElementStack::ElementRecord::~ElementRecord()
134 {
135 }
136
137 void HTMLElementStack::ElementRecord::replaceElement(PassRefPtr<Element> element)
138 {
139     ASSERT(element);
140     // FIXME: Should this call finishParsingChildren?
141     m_element = element;
142 }
143
144 bool HTMLElementStack::ElementRecord::isAbove(ElementRecord* other) const
145 {
146     for (ElementRecord* below = next(); below; below = below->next()) {
147         if (below == other)
148             return true;
149     }
150     return false;
151 }
152
153 HTMLElementStack::HTMLElementStack()
154     : m_htmlElement(0)
155     , m_headElement(0)
156     , m_bodyElement(0)
157 {
158 }
159
160 HTMLElementStack::~HTMLElementStack()
161 {
162 }
163
164 bool HTMLElementStack::hasOnlyOneElement() const
165 {
166     return !topRecord()->next();
167 }
168
169 bool HTMLElementStack::secondElementIsHTMLBodyElement() const
170 {
171     // This is used the fragment case of <body> and <frameset> in the "in body"
172     // insertion mode.
173     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#parsing-main-inbody
174     ASSERT(m_htmlElement);
175     // If we have a body element, it must always be the second element on the
176     // stack, as we always start with an html element, and any other element
177     // would cause the implicit creation of a body element.
178     return !!m_bodyElement;
179 }
180
181 void HTMLElementStack::popHTMLHeadElement()
182 {
183     ASSERT(top() == m_headElement);
184     m_headElement = 0;
185     popCommon();
186 }
187
188 void HTMLElementStack::popHTMLBodyElement()
189 {
190     ASSERT(top() == m_bodyElement);
191     m_bodyElement = 0;
192     popCommon();
193 }
194
195 void HTMLElementStack::popAll()
196 {
197     m_htmlElement = 0;
198     m_headElement = 0;
199     m_bodyElement = 0;
200     while (m_top) {
201         top()->finishParsingChildren();
202         m_top = m_top->releaseNext();
203     }
204 }
205
206 void HTMLElementStack::pop()
207 {
208     ASSERT(!top()->hasTagName(HTMLNames::headTag));
209     popCommon();
210 }
211
212 void HTMLElementStack::popUntil(const AtomicString& tagName)
213 {
214     while (!top()->hasLocalName(tagName)) {
215         // pop() will ASSERT at <body> if callers fail to check that there is an
216         // element with localName |tagName| on the stack of open elements.
217         pop();
218     }
219 }
220
221 void HTMLElementStack::popUntilPopped(const AtomicString& tagName)
222 {
223     popUntil(tagName);
224     pop();
225 }
226
227 void HTMLElementStack::popUntilNumberedHeaderElementPopped()
228 {
229     while (!isNumberedHeaderElement(top()))
230         pop();
231     pop();
232 }
233
234 void HTMLElementStack::popUntil(Element* element)
235 {
236     while (top() != element)
237         pop();
238 }
239
240 void HTMLElementStack::popUntilPopped(Element* element)
241 {
242     popUntil(element);
243     pop();
244 }
245
246 void HTMLElementStack::popUntilTableScopeMarker()
247 {
248     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-context
249     while (!isTableScopeMarker(top()))
250         pop();
251 }
252
253 void HTMLElementStack::popUntilTableBodyScopeMarker()
254 {
255     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-body-context
256     while (!isTableBodyScopeMarker(top()))
257         pop();
258 }
259
260 void HTMLElementStack::popUntilTableRowScopeMarker()
261 {
262     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-row-context
263     while (!isTableRowScopeMarker(top()))
264         pop();
265 }
266
267 void HTMLElementStack::popUntilForeignContentScopeMarker()
268 {
269     while (!isForeignContentScopeMarker(top()))
270         pop();
271 }
272
273 void HTMLElementStack::pushHTMLHtmlElement(PassRefPtr<Element> element)
274 {
275     ASSERT(!m_top); // <html> should always be the bottom of the stack.
276     ASSERT(element->hasTagName(HTMLNames::htmlTag));
277     ASSERT(!m_htmlElement);
278     m_htmlElement = element.get();
279     pushCommon(element);
280 }
281
282 void HTMLElementStack::pushHTMLHeadElement(PassRefPtr<Element> element)
283 {
284     ASSERT(element->hasTagName(HTMLNames::headTag));
285     ASSERT(!m_headElement);
286     m_headElement = element.get();
287     pushCommon(element);
288 }
289
290 void HTMLElementStack::pushHTMLBodyElement(PassRefPtr<Element> element)
291 {
292     ASSERT(element->hasTagName(HTMLNames::bodyTag));
293     ASSERT(!m_bodyElement);
294     m_bodyElement = element.get();
295     pushCommon(element);
296 }
297
298 void HTMLElementStack::push(PassRefPtr<Element> element)
299 {
300     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
301     ASSERT(!element->hasTagName(HTMLNames::headTag));
302     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
303     ASSERT(m_htmlElement);
304     pushCommon(element);
305 }
306
307 void HTMLElementStack::insertAbove(PassRefPtr<Element> element, ElementRecord* recordBelow)
308 {
309     ASSERT(element);
310     ASSERT(recordBelow);
311     ASSERT(m_top);
312     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
313     ASSERT(!element->hasTagName(HTMLNames::headTag));
314     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
315     ASSERT(m_htmlElement);
316     if (recordBelow == m_top) {
317         push(element);
318         return;
319     }
320
321     for (ElementRecord* recordAbove = m_top.get(); recordAbove; recordAbove = recordAbove->next()) {
322         if (recordAbove->next() != recordBelow)
323             continue;
324
325         recordAbove->setNext(adoptPtr(new ElementRecord(element, recordAbove->releaseNext())));
326         recordAbove->next()->element()->beginParsingChildren();
327         return;
328     }
329     ASSERT_NOT_REACHED();
330 }
331
332 HTMLElementStack::ElementRecord* HTMLElementStack::topRecord() const
333 {
334     ASSERT(m_top);
335     return m_top.get();
336 }
337
338 Element* HTMLElementStack::oneBelowTop() const
339 {
340     // We should never be calling this if it could be 0.
341     ASSERT(m_top);
342     ASSERT(m_top->next());
343     return m_top->next()->element();
344 }
345
346 Element* HTMLElementStack::bottom() const
347 {
348     return htmlElement();
349 }
350
351 void HTMLElementStack::removeHTMLHeadElement(Element* element)
352 {
353     ASSERT(m_headElement == element);
354     if (m_top->element() == element) {
355         popHTMLHeadElement();
356         return;
357     }
358     m_headElement = 0;
359     removeNonTopCommon(element);
360 }
361
362 void HTMLElementStack::remove(Element* element)
363 {
364     ASSERT(!element->hasTagName(HTMLNames::headTag));
365     if (m_top->element() == element) {
366         pop();
367         return;
368     }
369     removeNonTopCommon(element);
370 }
371
372 HTMLElementStack::ElementRecord* HTMLElementStack::find(Element* element) const
373 {
374     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
375         if (pos->element() == element)
376             return pos;
377     }
378     return 0;
379 }
380
381 HTMLElementStack::ElementRecord* HTMLElementStack::topmost(const AtomicString& tagName) const
382 {
383     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
384         if (pos->element()->hasLocalName(tagName))
385             return pos;
386     }
387     return 0;
388 }
389
390 bool HTMLElementStack::contains(Element* element) const
391 {
392     return !!find(element);
393 }
394
395 bool HTMLElementStack::contains(const AtomicString& tagName) const
396 {
397     return !!topmost(tagName);
398 }
399
400 template <bool isMarker(Element*)>
401 bool inScopeCommon(HTMLElementStack::ElementRecord* top, const AtomicString& targetTag)
402 {
403     for (HTMLElementStack::ElementRecord* pos = top; pos; pos = pos->next()) {
404         Element* element = pos->element();
405         if (element->hasLocalName(targetTag))
406             return true;
407         if (isMarker(element))
408             return false;
409     }
410     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
411     return false;
412 }
413
414 bool HTMLElementStack::hasOnlyHTMLElementsInScope() const
415 {
416     for (ElementRecord* record = m_top.get(); record; record = record->next()) {
417         Element* element = record->element();
418         if (element->namespaceURI() != xhtmlNamespaceURI)
419             return false;
420         if (isScopeMarker(element))
421             return true;
422     }
423     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
424     return true;
425 }
426
427 bool HTMLElementStack::hasNumberedHeaderElementInScope() const
428 {
429     for (ElementRecord* record = m_top.get(); record; record = record->next()) {
430         Element* element = record->element();
431         if (isNumberedHeaderElement(element))
432             return true;
433         if (isScopeMarker(element))
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 (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
443         Element* element = pos->element();
444         if (element == targetElement)
445             return true;
446         if (isScopeMarker(element))
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 AtomicString& targetTag) const
454 {
455     return inScopeCommon<isScopeMarker>(m_top.get(), targetTag);
456 }
457
458 bool HTMLElementStack::inScope(const QualifiedName& tagName) const
459 {
460     // FIXME: Is localName() right for non-html elements?
461     return inScope(tagName.localName());
462 }
463
464 bool HTMLElementStack::inListItemScope(const AtomicString& targetTag) const
465 {
466     return inScopeCommon<isListItemScopeMarker>(m_top.get(), targetTag);
467 }
468
469 bool HTMLElementStack::inListItemScope(const QualifiedName& tagName) const
470 {
471     // FIXME: Is localName() right for non-html elements?
472     return inListItemScope(tagName.localName());
473 }
474
475 bool HTMLElementStack::inTableScope(const AtomicString& targetTag) const
476 {
477     return inScopeCommon<isTableScopeMarker>(m_top.get(), targetTag);
478 }
479
480 bool HTMLElementStack::inTableScope(const QualifiedName& tagName) const
481 {
482     // FIXME: Is localName() right for non-html elements?
483     return inTableScope(tagName.localName());
484 }
485
486 bool HTMLElementStack::inButtonScope(const AtomicString& targetTag) const
487 {
488     return inScopeCommon<isButtonScopeMarker>(m_top.get(), targetTag);
489 }
490
491 bool HTMLElementStack::inButtonScope(const QualifiedName& tagName) const
492 {
493     // FIXME: Is localName() right for non-html elements?
494     return inButtonScope(tagName.localName());
495 }
496
497 bool HTMLElementStack::inSelectScope(const AtomicString& targetTag) const
498 {
499     return inScopeCommon<isSelectScopeMarker>(m_top.get(), targetTag);
500 }
501
502 bool HTMLElementStack::inSelectScope(const QualifiedName& tagName) const
503 {
504     // FIXME: Is localName() right for non-html elements?
505     return inSelectScope(tagName.localName());
506 }
507
508 Element* HTMLElementStack::htmlElement() const
509 {
510     ASSERT(m_htmlElement);
511     return m_htmlElement;
512 }
513
514 Element* HTMLElementStack::headElement() const
515 {
516     ASSERT(m_headElement);
517     return m_headElement;
518 }
519
520 Element* HTMLElementStack::bodyElement() const
521 {
522     ASSERT(m_bodyElement);
523     return m_bodyElement;
524 }
525
526 void HTMLElementStack::pushCommon(PassRefPtr<Element> element)
527 {
528     ASSERT(m_htmlElement);
529     m_top = adoptPtr(new ElementRecord(element, m_top.release()));
530     top()->beginParsingChildren();
531 }
532
533 void HTMLElementStack::popCommon()
534 {
535     ASSERT(!top()->hasTagName(HTMLNames::htmlTag));
536     ASSERT(!top()->hasTagName(HTMLNames::headTag) || !m_headElement);
537     ASSERT(!top()->hasTagName(HTMLNames::bodyTag) || !m_bodyElement);
538     top()->finishParsingChildren();
539     m_top = m_top->releaseNext();
540 }
541
542 void HTMLElementStack::removeNonTopCommon(Element* element)
543 {
544     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
545     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
546     ASSERT(top() != element);
547     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
548         if (pos->next()->element() == element) {
549             // FIXME: Is it OK to call finishParsingChildren()
550             // when the children aren't actually finished?
551             element->finishParsingChildren();
552             pos->setNext(pos->next()->releaseNext());
553             return;
554         }
555     }
556     ASSERT_NOT_REACHED();
557 }
558
559 #ifndef NDEBUG
560
561 void HTMLElementStack::show()
562 {
563     for (ElementRecord* record = m_top.get(); record; record = record->next())
564         record->element()->showNode();
565 }
566
567 #endif
568
569 }