2010-07-09 Eric Seidel <eric@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 isScopeMarker(Element* element)
44 {
45     return element->hasTagName(appletTag)
46         || element->hasTagName(buttonTag)
47         || element->hasTagName(captionTag)
48 #if ENABLE(SVG_FOREIGN_OBJECT)
49         || element->hasTagName(SVGNames::foreignObjectTag)
50 #endif
51         || element->hasTagName(htmlTag)
52         || element->hasTagName(marqueeTag)
53         || element->hasTagName(objectTag)
54         || element->hasTagName(tableTag)
55         || element->hasTagName(tdTag)
56         || element->hasTagName(thTag);
57 }
58
59 inline bool isListItemScopeMarker(Element* element)
60 {
61     return isScopeMarker(element)
62         || element->hasTagName(olTag)
63         || element->hasTagName(ulTag);
64 }
65
66 inline bool isTableScopeMarker(Element* element)
67 {
68     return element->hasTagName(tableTag)
69         || element->hasTagName(htmlTag);
70 }
71
72 inline bool isTableBodyScopeMarker(Element* element)
73 {
74     return element->hasTagName(tbodyTag)
75         || element->hasTagName(tfootTag)
76         || element->hasTagName(theadTag)
77         || element->hasTagName(htmlTag);
78 }
79
80 inline bool isTableRowScopeMarker(Element* element)
81 {
82     return element->hasTagName(trTag)
83         || element->hasTagName(htmlTag);
84 }
85
86 }
87
88 HTMLElementStack::ElementRecord::ElementRecord(PassRefPtr<Element> element, PassOwnPtr<ElementRecord> next)
89     : m_element(element)
90     , m_next(next)
91 {
92     ASSERT(m_element);
93 }
94
95 HTMLElementStack::ElementRecord::~ElementRecord()
96 {
97 }
98
99 void HTMLElementStack::ElementRecord::replaceElement(PassRefPtr<Element> element)
100 {
101     ASSERT(element);
102     // FIXME: Should this call finishParsingChildren?
103     m_element = element;
104 }
105
106 bool HTMLElementStack::ElementRecord::isAbove(ElementRecord* other) const
107 {
108     for (ElementRecord* below = next(); below; below = below->next()) {
109         if (below == other)
110             return true;
111     }
112     return false;
113 }
114
115 HTMLElementStack::HTMLElementStack()
116     : m_htmlElement(0)
117     , m_headElement(0)
118     , m_bodyElement(0)
119 {
120 }
121
122 HTMLElementStack::~HTMLElementStack()
123 {
124 }
125
126 void HTMLElementStack::popHTMLHeadElement()
127 {
128     ASSERT(top() == m_headElement);
129     m_headElement = 0;
130     popCommon();
131 }
132
133 void HTMLElementStack::popHTMLBodyElement()
134 {
135     ASSERT(top() == m_bodyElement);
136     m_bodyElement = 0;
137     popCommon();
138 }
139
140 void HTMLElementStack::pop()
141 {
142     ASSERT(!top()->hasTagName(HTMLNames::headTag));
143     popCommon();
144 }
145
146 void HTMLElementStack::popUntil(const AtomicString& tagName)
147 {
148     while (!top()->hasLocalName(tagName)) {
149         // pop() will ASSERT at <body> if callers fail to check that there is an
150         // element with localName |tagName| on the stack of open elements.
151         pop();
152     }
153 }
154
155 void HTMLElementStack::popUntilPopped(const AtomicString& tagName)
156 {
157     popUntil(tagName);
158     pop();
159 }
160
161 void HTMLElementStack::popUntil(Element* element)
162 {
163     while (top() != element)
164         pop();
165 }
166
167 void HTMLElementStack::popUntilPopped(Element* element)
168 {
169     popUntil(element);
170     pop();
171 }
172
173 void HTMLElementStack::popUntilTableScopeMarker()
174 {
175     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-context
176     while (!isTableScopeMarker(top()))
177         pop();
178 }
179
180 void HTMLElementStack::popUntilTableBodyScopeMarker()
181 {
182     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-body-context
183     while (!isTableBodyScopeMarker(top()))
184         pop();
185 }
186
187 void HTMLElementStack::popUntilTableRowScopeMarker()
188 {
189     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-row-context
190     while (!isTableRowScopeMarker(top()))
191         pop();
192 }
193
194 void HTMLElementStack::pushHTMLHtmlElement(PassRefPtr<Element> element)
195 {
196     ASSERT(!m_top); // <html> should always be the bottom of the stack.
197     ASSERT(element->hasTagName(HTMLNames::htmlTag));
198     ASSERT(!m_htmlElement);
199     m_htmlElement = element.get();
200     pushCommon(element);
201 }
202
203 void HTMLElementStack::pushHTMLHeadElement(PassRefPtr<Element> element)
204 {
205     ASSERT(element->hasTagName(HTMLNames::headTag));
206     ASSERT(!m_headElement);
207     m_headElement = element.get();
208     pushCommon(element);
209 }
210
211 void HTMLElementStack::pushHTMLBodyElement(PassRefPtr<Element> element)
212 {
213     ASSERT(element->hasTagName(HTMLNames::bodyTag));
214     ASSERT(!m_bodyElement);
215     m_bodyElement = element.get();
216     pushCommon(element);
217 }
218
219 void HTMLElementStack::push(PassRefPtr<Element> element)
220 {
221     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
222     ASSERT(!element->hasTagName(HTMLNames::headTag));
223     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
224     ASSERT(m_htmlElement);
225     pushCommon(element);
226 }
227
228 void HTMLElementStack::insertAbove(PassRefPtr<Element> element, ElementRecord* recordBelow)
229 {
230     ASSERT(element);
231     ASSERT(recordBelow);
232     ASSERT(m_top);
233     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
234     ASSERT(!element->hasTagName(HTMLNames::headTag));
235     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
236     ASSERT(m_htmlElement);
237     if (recordBelow == m_top) {
238         push(element);
239         return;
240     }
241
242     for (ElementRecord* recordAbove = m_top.get(); recordAbove; recordAbove = recordAbove->next()) {
243         if (recordAbove->next() != recordBelow)
244             continue;
245
246         recordAbove->setNext(new ElementRecord(element, recordAbove->releaseNext()));
247         recordAbove->next()->element()->beginParsingChildren();
248         return;
249     }
250     ASSERT_NOT_REACHED();
251 }
252
253 HTMLElementStack::ElementRecord* HTMLElementStack::topRecord() const
254 {
255     ASSERT(m_top);
256     return m_top.get();
257 }
258
259 Element* HTMLElementStack::top() const
260 {
261     ASSERT(m_top->element());
262     return m_top->element();
263 }
264
265 Element* HTMLElementStack::oneBelowTop() const
266 {
267     // We should never be calling this if it could be 0.
268     ASSERT(m_top);
269     ASSERT(m_top->next());
270     return m_top->next()->element();
271 }
272
273 Element* HTMLElementStack::bottom() const
274 {
275     return htmlElement();
276 }
277
278 void HTMLElementStack::removeHTMLHeadElement(Element* element)
279 {
280     ASSERT(m_headElement == element);
281     if (m_top->element() == element) {
282         popHTMLHeadElement();
283         return;
284     }
285     m_headElement = 0;
286     removeNonTopCommon(element);
287 }
288
289 void HTMLElementStack::remove(Element* element)
290 {
291     ASSERT(!element->hasTagName(HTMLNames::headTag));
292     if (m_top->element() == element) {
293         pop();
294         return;
295     }
296     removeNonTopCommon(element);
297 }
298
299 HTMLElementStack::ElementRecord* HTMLElementStack::find(Element* element) const
300 {
301     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
302         if (pos->element() == element)
303             return pos;
304     }
305     return 0;
306 }
307
308 HTMLElementStack::ElementRecord* HTMLElementStack::topmost(const AtomicString& tagName) const
309 {
310     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
311         if (pos->element()->hasLocalName(tagName))
312             return pos;
313     }
314     return 0;
315 }
316
317 bool HTMLElementStack::contains(Element* element) const
318 {
319     return !!find(element);
320 }
321
322 template <bool isMarker(Element*)>
323 bool inScopeCommon(HTMLElementStack::ElementRecord* top, const AtomicString& targetTag)
324 {
325     for (HTMLElementStack::ElementRecord* pos = top; pos; pos = pos->next()) {
326         Element* element = pos->element();
327         if (element->hasLocalName(targetTag))
328             return true;
329         if (isMarker(element))
330             return false;
331     }
332     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
333     return false;
334 }
335
336 bool HTMLElementStack::inScope(Element* targetElement) const
337 {
338     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
339         Element* element = pos->element();
340         if (element == targetElement)
341             return true;
342         if (isScopeMarker(element))
343             return false;
344     }
345     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
346     return false;
347 }
348
349 bool HTMLElementStack::inScope(const AtomicString& targetTag) const
350 {
351     return inScopeCommon<isScopeMarker>(m_top.get(), targetTag);
352 }
353
354 bool HTMLElementStack::inScope(const QualifiedName& tagName) const
355 {
356     // FIXME: Is localName() right for non-html elements?
357     return inScope(tagName.localName());
358 }
359
360 bool HTMLElementStack::inListItemScope(const AtomicString& targetTag) const
361 {
362     return inScopeCommon<isListItemScopeMarker>(m_top.get(), targetTag);
363 }
364
365 bool HTMLElementStack::inListItemScope(const QualifiedName& tagName) const
366 {
367     // FIXME: Is localName() right for non-html elements?
368     return inListItemScope(tagName.localName());
369 }
370
371 bool HTMLElementStack::inTableScope(const AtomicString& targetTag) const
372 {
373     return inScopeCommon<isTableScopeMarker>(m_top.get(), targetTag);
374 }
375
376 bool HTMLElementStack::inTableScope(const QualifiedName& tagName) const
377 {
378     // FIXME: Is localName() right for non-html elements?
379     return inTableScope(tagName.localName());
380 }
381
382 Element* HTMLElementStack::htmlElement() const
383 {
384     ASSERT(m_htmlElement);
385     return m_htmlElement;
386 }
387
388 Element* HTMLElementStack::headElement() const
389 {
390     ASSERT(m_headElement);
391     return m_headElement;
392 }
393
394 Element* HTMLElementStack::bodyElement() const
395 {
396     ASSERT(m_bodyElement);
397     return m_bodyElement;
398 }
399
400 void HTMLElementStack::pushCommon(PassRefPtr<Element> element)
401 {
402     ASSERT(m_htmlElement);
403     m_top.set(new ElementRecord(element, m_top.release()));
404     top()->beginParsingChildren();
405 }
406
407 void HTMLElementStack::popCommon()
408 {
409     ASSERT(!top()->hasTagName(HTMLNames::htmlTag));
410     ASSERT(!top()->hasTagName(HTMLNames::headTag) || !m_headElement);
411     ASSERT(!top()->hasTagName(HTMLNames::bodyTag) || !m_bodyElement);
412     top()->finishParsingChildren();
413     m_top = m_top->releaseNext();
414 }
415
416 void HTMLElementStack::removeNonTopCommon(Element* element)
417 {
418     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
419     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
420     ASSERT(top() != element);
421     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
422         if (pos->next()->element() == element) {
423             // FIXME: Is it OK to call finishParsingChildren()
424             // when the children aren't actually finished?
425             element->finishParsingChildren();
426             pos->setNext(pos->next()->releaseNext());
427             return;
428         }
429     }
430     ASSERT_NOT_REACHED();
431 }
432
433 #ifndef NDEBUG
434
435 void HTMLElementStack::show()
436 {
437     for (ElementRecord* record = m_top.get(); record; record = record->next())
438         record->element()->showNode();
439 }
440
441 #endif
442
443 }