2010-08-24 Adam Barth <abarth@webkit.org>
[WebKit-https.git] / WebCore / html / 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 <wtf/PassOwnPtr.h>
32
33 #if ENABLE(SVG)
34 #include "SVGNames.h"
35 #endif
36
37 namespace WebCore {
38
39 using namespace HTMLNames;
40
41 namespace {
42
43 inline bool isNumberedHeaderElement(Element* element)
44 {
45     return element->hasTagName(h1Tag)
46         || element->hasTagName(h2Tag)
47         || element->hasTagName(h3Tag)
48         || element->hasTagName(h4Tag)
49         || element->hasTagName(h5Tag)
50         || element->hasTagName(h6Tag);
51 }
52
53 inline bool isScopeMarker(Element* element)
54 {
55     return element->hasTagName(appletTag)
56         || element->hasTagName(captionTag)
57 #if ENABLE(SVG_FOREIGN_OBJECT)
58         || element->hasTagName(SVGNames::foreignObjectTag)
59 #endif
60         || element->hasTagName(htmlTag)
61         || element->hasTagName(marqueeTag)
62         || element->hasTagName(objectTag)
63         || element->hasTagName(tableTag)
64         || element->hasTagName(tdTag)
65         || element->hasTagName(thTag);
66 }
67
68 inline bool isListItemScopeMarker(Element* element)
69 {
70     return isScopeMarker(element)
71         || element->hasTagName(olTag)
72         || element->hasTagName(ulTag);
73 }
74
75 inline bool isTableScopeMarker(Element* element)
76 {
77     return element->hasTagName(tableTag)
78         || element->hasTagName(htmlTag);
79 }
80
81 inline bool isTableBodyScopeMarker(Element* element)
82 {
83     return element->hasTagName(tbodyTag)
84         || element->hasTagName(tfootTag)
85         || element->hasTagName(theadTag)
86         || element->hasTagName(htmlTag);
87 }
88
89 inline bool isTableRowScopeMarker(Element* element)
90 {
91     return element->hasTagName(trTag)
92         || element->hasTagName(htmlTag);
93 }
94
95 inline bool isButtonScopeMarker(Element* element)
96 {
97     return isScopeMarker(element)
98         || element->hasTagName(buttonTag);
99 }
100
101 }
102
103 HTMLElementStack::ElementRecord::ElementRecord(PassRefPtr<Element> element, PassOwnPtr<ElementRecord> next)
104     : m_element(element)
105     , m_next(next)
106 {
107     ASSERT(m_element);
108 }
109
110 HTMLElementStack::ElementRecord::~ElementRecord()
111 {
112 }
113
114 void HTMLElementStack::ElementRecord::replaceElement(PassRefPtr<Element> element)
115 {
116     ASSERT(element);
117     // FIXME: Should this call finishParsingChildren?
118     m_element = element;
119 }
120
121 bool HTMLElementStack::ElementRecord::isAbove(ElementRecord* other) const
122 {
123     for (ElementRecord* below = next(); below; below = below->next()) {
124         if (below == other)
125             return true;
126     }
127     return false;
128 }
129
130 HTMLElementStack::HTMLElementStack()
131     : m_htmlElement(0)
132     , m_headElement(0)
133     , m_bodyElement(0)
134 {
135 }
136
137 HTMLElementStack::~HTMLElementStack()
138 {
139 }
140
141 bool HTMLElementStack::hasOnlyOneElement() const
142 {
143     return !topRecord()->next();
144 }
145
146 bool HTMLElementStack::secondElementIsHTMLBodyElement() const
147 {
148     // This is used the fragment case of <body> and <frameset> in the "in body"
149     // insertion mode.
150     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#parsing-main-inbody
151     ASSERT(m_htmlElement);
152     // If we have a body element, it must always be the second element on the
153     // stack, as we always start with an html element, and any other element
154     // would cause the implicit creation of a body element.
155     return !!m_bodyElement;
156 }
157
158 void HTMLElementStack::popHTMLHeadElement()
159 {
160     ASSERT(top() == m_headElement);
161     m_headElement = 0;
162     popCommon();
163 }
164
165 void HTMLElementStack::popHTMLBodyElement()
166 {
167     ASSERT(top() == m_bodyElement);
168     m_bodyElement = 0;
169     popCommon();
170 }
171
172 void HTMLElementStack::popAll()
173 {
174     m_htmlElement = 0;
175     m_headElement = 0;
176     m_bodyElement = 0;
177     while (m_top) {
178         top()->finishParsingChildren();
179         m_top = m_top->releaseNext();
180     }
181 }
182
183 void HTMLElementStack::pop()
184 {
185     ASSERT(!top()->hasTagName(HTMLNames::headTag));
186     popCommon();
187 }
188
189 void HTMLElementStack::popUntilElementWithNamespace(const AtomicString& namespaceURI)
190 {
191     while (top()->namespaceURI() != namespaceURI)
192         pop();
193 }
194
195 void HTMLElementStack::popUntil(const AtomicString& tagName)
196 {
197     while (!top()->hasLocalName(tagName)) {
198         // pop() will ASSERT at <body> if callers fail to check that there is an
199         // element with localName |tagName| on the stack of open elements.
200         pop();
201     }
202 }
203
204 void HTMLElementStack::popUntilPopped(const AtomicString& tagName)
205 {
206     popUntil(tagName);
207     pop();
208 }
209
210 void HTMLElementStack::popUntilNumberedHeaderElementPopped()
211 {
212     while (!isNumberedHeaderElement(top()))
213         pop();
214     pop();
215 }
216
217 void HTMLElementStack::popUntil(Element* element)
218 {
219     while (top() != element)
220         pop();
221 }
222
223 void HTMLElementStack::popUntilPopped(Element* element)
224 {
225     popUntil(element);
226     pop();
227 }
228
229 void HTMLElementStack::popUntilTableScopeMarker()
230 {
231     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-context
232     while (!isTableScopeMarker(top()))
233         pop();
234 }
235
236 void HTMLElementStack::popUntilTableBodyScopeMarker()
237 {
238     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-body-context
239     while (!isTableBodyScopeMarker(top()))
240         pop();
241 }
242
243 void HTMLElementStack::popUntilTableRowScopeMarker()
244 {
245     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-row-context
246     while (!isTableRowScopeMarker(top()))
247         pop();
248 }
249
250 void HTMLElementStack::pushHTMLHtmlElement(PassRefPtr<Element> element)
251 {
252     ASSERT(!m_top); // <html> should always be the bottom of the stack.
253     ASSERT(element->hasTagName(HTMLNames::htmlTag));
254     ASSERT(!m_htmlElement);
255     m_htmlElement = element.get();
256     pushCommon(element);
257 }
258
259 void HTMLElementStack::pushHTMLHeadElement(PassRefPtr<Element> element)
260 {
261     ASSERT(element->hasTagName(HTMLNames::headTag));
262     ASSERT(!m_headElement);
263     m_headElement = element.get();
264     pushCommon(element);
265 }
266
267 void HTMLElementStack::pushHTMLBodyElement(PassRefPtr<Element> element)
268 {
269     ASSERT(element->hasTagName(HTMLNames::bodyTag));
270     ASSERT(!m_bodyElement);
271     m_bodyElement = element.get();
272     pushCommon(element);
273 }
274
275 void HTMLElementStack::push(PassRefPtr<Element> element)
276 {
277     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
278     ASSERT(!element->hasTagName(HTMLNames::headTag));
279     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
280     ASSERT(m_htmlElement);
281     pushCommon(element);
282 }
283
284 void HTMLElementStack::insertAbove(PassRefPtr<Element> element, ElementRecord* recordBelow)
285 {
286     ASSERT(element);
287     ASSERT(recordBelow);
288     ASSERT(m_top);
289     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
290     ASSERT(!element->hasTagName(HTMLNames::headTag));
291     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
292     ASSERT(m_htmlElement);
293     if (recordBelow == m_top) {
294         push(element);
295         return;
296     }
297
298     for (ElementRecord* recordAbove = m_top.get(); recordAbove; recordAbove = recordAbove->next()) {
299         if (recordAbove->next() != recordBelow)
300             continue;
301
302         recordAbove->setNext(adoptPtr(new ElementRecord(element, recordAbove->releaseNext())));
303         recordAbove->next()->element()->beginParsingChildren();
304         return;
305     }
306     ASSERT_NOT_REACHED();
307 }
308
309 HTMLElementStack::ElementRecord* HTMLElementStack::topRecord() const
310 {
311     ASSERT(m_top);
312     return m_top.get();
313 }
314
315 Element* HTMLElementStack::oneBelowTop() const
316 {
317     // We should never be calling this if it could be 0.
318     ASSERT(m_top);
319     ASSERT(m_top->next());
320     return m_top->next()->element();
321 }
322
323 Element* HTMLElementStack::bottom() const
324 {
325     return htmlElement();
326 }
327
328 void HTMLElementStack::removeHTMLHeadElement(Element* element)
329 {
330     ASSERT(m_headElement == element);
331     if (m_top->element() == element) {
332         popHTMLHeadElement();
333         return;
334     }
335     m_headElement = 0;
336     removeNonTopCommon(element);
337 }
338
339 void HTMLElementStack::remove(Element* element)
340 {
341     ASSERT(!element->hasTagName(HTMLNames::headTag));
342     if (m_top->element() == element) {
343         pop();
344         return;
345     }
346     removeNonTopCommon(element);
347 }
348
349 HTMLElementStack::ElementRecord* HTMLElementStack::find(Element* element) const
350 {
351     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
352         if (pos->element() == element)
353             return pos;
354     }
355     return 0;
356 }
357
358 HTMLElementStack::ElementRecord* HTMLElementStack::topmost(const AtomicString& tagName) const
359 {
360     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
361         if (pos->element()->hasLocalName(tagName))
362             return pos;
363     }
364     return 0;
365 }
366
367 bool HTMLElementStack::contains(Element* element) const
368 {
369     return !!find(element);
370 }
371
372 bool HTMLElementStack::contains(const AtomicString& tagName) const
373 {
374     return !!topmost(tagName);
375 }
376
377 template <bool isMarker(Element*)>
378 bool inScopeCommon(HTMLElementStack::ElementRecord* top, const AtomicString& targetTag)
379 {
380     for (HTMLElementStack::ElementRecord* pos = top; pos; pos = pos->next()) {
381         Element* element = pos->element();
382         if (element->hasLocalName(targetTag))
383             return true;
384         if (isMarker(element))
385             return false;
386     }
387     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
388     return false;
389 }
390
391 bool HTMLElementStack::hasOnlyHTMLElementsInScope() const
392 {
393     for (ElementRecord* record = m_top.get(); record; record = record->next()) {
394         Element* element = record->element();
395         if (element->namespaceURI() != xhtmlNamespaceURI)
396             return false;
397         if (isScopeMarker(element))
398             return true;
399     }
400     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
401     return true;
402 }
403
404 bool HTMLElementStack::hasNumberedHeaderElementInScope() const
405 {
406     for (ElementRecord* record = m_top.get(); record; record = record->next()) {
407         Element* element = record->element();
408         if (isNumberedHeaderElement(element))
409             return true;
410         if (isScopeMarker(element))
411             return false;
412     }
413     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
414     return false;
415 }
416
417 bool HTMLElementStack::inScope(Element* targetElement) const
418 {
419     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
420         Element* element = pos->element();
421         if (element == targetElement)
422             return true;
423         if (isScopeMarker(element))
424             return false;
425     }
426     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
427     return false;
428 }
429
430 bool HTMLElementStack::inScope(const AtomicString& targetTag) const
431 {
432     return inScopeCommon<isScopeMarker>(m_top.get(), targetTag);
433 }
434
435 bool HTMLElementStack::inScope(const QualifiedName& tagName) const
436 {
437     // FIXME: Is localName() right for non-html elements?
438     return inScope(tagName.localName());
439 }
440
441 bool HTMLElementStack::inListItemScope(const AtomicString& targetTag) const
442 {
443     return inScopeCommon<isListItemScopeMarker>(m_top.get(), targetTag);
444 }
445
446 bool HTMLElementStack::inListItemScope(const QualifiedName& tagName) const
447 {
448     // FIXME: Is localName() right for non-html elements?
449     return inListItemScope(tagName.localName());
450 }
451
452 bool HTMLElementStack::inTableScope(const AtomicString& targetTag) const
453 {
454     return inScopeCommon<isTableScopeMarker>(m_top.get(), targetTag);
455 }
456
457 bool HTMLElementStack::inTableScope(const QualifiedName& tagName) const
458 {
459     // FIXME: Is localName() right for non-html elements?
460     return inTableScope(tagName.localName());
461 }
462
463 bool HTMLElementStack::inButtonScope(const AtomicString& targetTag) const
464 {
465     return inScopeCommon<isButtonScopeMarker>(m_top.get(), targetTag);
466 }
467
468 bool HTMLElementStack::inButtonScope(const QualifiedName& tagName) const
469 {
470     // FIXME: Is localName() right for non-html elements?
471     return inButtonScope(tagName.localName());
472 }
473
474 Element* HTMLElementStack::htmlElement() const
475 {
476     ASSERT(m_htmlElement);
477     return m_htmlElement;
478 }
479
480 Element* HTMLElementStack::headElement() const
481 {
482     ASSERT(m_headElement);
483     return m_headElement;
484 }
485
486 Element* HTMLElementStack::bodyElement() const
487 {
488     ASSERT(m_bodyElement);
489     return m_bodyElement;
490 }
491
492 void HTMLElementStack::pushCommon(PassRefPtr<Element> element)
493 {
494     ASSERT(m_htmlElement);
495     m_top = adoptPtr(new ElementRecord(element, m_top.release()));
496     top()->beginParsingChildren();
497 }
498
499 void HTMLElementStack::popCommon()
500 {
501     ASSERT(!top()->hasTagName(HTMLNames::htmlTag));
502     ASSERT(!top()->hasTagName(HTMLNames::headTag) || !m_headElement);
503     ASSERT(!top()->hasTagName(HTMLNames::bodyTag) || !m_bodyElement);
504     top()->finishParsingChildren();
505     m_top = m_top->releaseNext();
506 }
507
508 void HTMLElementStack::removeNonTopCommon(Element* element)
509 {
510     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
511     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
512     ASSERT(top() != element);
513     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
514         if (pos->next()->element() == element) {
515             // FIXME: Is it OK to call finishParsingChildren()
516             // when the children aren't actually finished?
517             element->finishParsingChildren();
518             pos->setNext(pos->next()->releaseNext());
519             return;
520         }
521     }
522     ASSERT_NOT_REACHED();
523 }
524
525 #ifndef NDEBUG
526
527 void HTMLElementStack::show()
528 {
529     for (ElementRecord* record = m_top.get(); record; record = record->next())
530         record->element()->showNode();
531 }
532
533 #endif
534
535 }