2010-07-12 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::popUntilElementWithNamespace(const AtomicString& namespaceURI)
147 {
148     while (top()->namespaceURI() != namespaceURI)
149         pop();
150 }
151
152 void HTMLElementStack::popUntil(const AtomicString& tagName)
153 {
154     while (!top()->hasLocalName(tagName)) {
155         // pop() will ASSERT at <body> if callers fail to check that there is an
156         // element with localName |tagName| on the stack of open elements.
157         pop();
158     }
159 }
160
161 void HTMLElementStack::popUntilPopped(const AtomicString& tagName)
162 {
163     popUntil(tagName);
164     pop();
165 }
166
167 void HTMLElementStack::popUntil(Element* element)
168 {
169     while (top() != element)
170         pop();
171 }
172
173 void HTMLElementStack::popUntilPopped(Element* element)
174 {
175     popUntil(element);
176     pop();
177 }
178
179 void HTMLElementStack::popUntilTableScopeMarker()
180 {
181     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-context
182     while (!isTableScopeMarker(top()))
183         pop();
184 }
185
186 void HTMLElementStack::popUntilTableBodyScopeMarker()
187 {
188     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-body-context
189     while (!isTableBodyScopeMarker(top()))
190         pop();
191 }
192
193 void HTMLElementStack::popUntilTableRowScopeMarker()
194 {
195     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-row-context
196     while (!isTableRowScopeMarker(top()))
197         pop();
198 }
199
200 void HTMLElementStack::pushHTMLHtmlElement(PassRefPtr<Element> element)
201 {
202     ASSERT(!m_top); // <html> should always be the bottom of the stack.
203     ASSERT(element->hasTagName(HTMLNames::htmlTag));
204     ASSERT(!m_htmlElement);
205     m_htmlElement = element.get();
206     pushCommon(element);
207 }
208
209 void HTMLElementStack::pushHTMLHeadElement(PassRefPtr<Element> element)
210 {
211     ASSERT(element->hasTagName(HTMLNames::headTag));
212     ASSERT(!m_headElement);
213     m_headElement = element.get();
214     pushCommon(element);
215 }
216
217 void HTMLElementStack::pushHTMLBodyElement(PassRefPtr<Element> element)
218 {
219     ASSERT(element->hasTagName(HTMLNames::bodyTag));
220     ASSERT(!m_bodyElement);
221     m_bodyElement = element.get();
222     pushCommon(element);
223 }
224
225 void HTMLElementStack::push(PassRefPtr<Element> element)
226 {
227     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
228     ASSERT(!element->hasTagName(HTMLNames::headTag));
229     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
230     ASSERT(m_htmlElement);
231     pushCommon(element);
232 }
233
234 void HTMLElementStack::insertAbove(PassRefPtr<Element> element, ElementRecord* recordBelow)
235 {
236     ASSERT(element);
237     ASSERT(recordBelow);
238     ASSERT(m_top);
239     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
240     ASSERT(!element->hasTagName(HTMLNames::headTag));
241     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
242     ASSERT(m_htmlElement);
243     if (recordBelow == m_top) {
244         push(element);
245         return;
246     }
247
248     for (ElementRecord* recordAbove = m_top.get(); recordAbove; recordAbove = recordAbove->next()) {
249         if (recordAbove->next() != recordBelow)
250             continue;
251
252         recordAbove->setNext(new ElementRecord(element, recordAbove->releaseNext()));
253         recordAbove->next()->element()->beginParsingChildren();
254         return;
255     }
256     ASSERT_NOT_REACHED();
257 }
258
259 HTMLElementStack::ElementRecord* HTMLElementStack::topRecord() const
260 {
261     ASSERT(m_top);
262     return m_top.get();
263 }
264
265 Element* HTMLElementStack::top() const
266 {
267     ASSERT(m_top->element());
268     return m_top->element();
269 }
270
271 Element* HTMLElementStack::oneBelowTop() const
272 {
273     // We should never be calling this if it could be 0.
274     ASSERT(m_top);
275     ASSERT(m_top->next());
276     return m_top->next()->element();
277 }
278
279 Element* HTMLElementStack::bottom() const
280 {
281     return htmlElement();
282 }
283
284 void HTMLElementStack::removeHTMLHeadElement(Element* element)
285 {
286     ASSERT(m_headElement == element);
287     if (m_top->element() == element) {
288         popHTMLHeadElement();
289         return;
290     }
291     m_headElement = 0;
292     removeNonTopCommon(element);
293 }
294
295 void HTMLElementStack::remove(Element* element)
296 {
297     ASSERT(!element->hasTagName(HTMLNames::headTag));
298     if (m_top->element() == element) {
299         pop();
300         return;
301     }
302     removeNonTopCommon(element);
303 }
304
305 HTMLElementStack::ElementRecord* HTMLElementStack::find(Element* element) const
306 {
307     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
308         if (pos->element() == element)
309             return pos;
310     }
311     return 0;
312 }
313
314 HTMLElementStack::ElementRecord* HTMLElementStack::topmost(const AtomicString& tagName) const
315 {
316     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
317         if (pos->element()->hasLocalName(tagName))
318             return pos;
319     }
320     return 0;
321 }
322
323 bool HTMLElementStack::contains(Element* element) const
324 {
325     return !!find(element);
326 }
327
328 template <bool isMarker(Element*)>
329 bool inScopeCommon(HTMLElementStack::ElementRecord* top, const AtomicString& targetTag)
330 {
331     for (HTMLElementStack::ElementRecord* pos = top; pos; pos = pos->next()) {
332         Element* element = pos->element();
333         if (element->hasLocalName(targetTag))
334             return true;
335         if (isMarker(element))
336             return false;
337     }
338     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
339     return false;
340 }
341
342 bool HTMLElementStack::hasOnlyHTMLElementsInScope() const
343 {
344     for (ElementRecord* record = m_top.get(); record; record = record->next()) {
345         Element* element = record->element();
346         if (element->namespaceURI() != xhtmlNamespaceURI)
347             return false;
348         if (isScopeMarker(element))
349             return true;
350     }
351     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
352     return true;
353 }
354
355 bool HTMLElementStack::inScope(Element* targetElement) const
356 {
357     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
358         Element* element = pos->element();
359         if (element == targetElement)
360             return true;
361         if (isScopeMarker(element))
362             return false;
363     }
364     ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
365     return false;
366 }
367
368 bool HTMLElementStack::inScope(const AtomicString& targetTag) const
369 {
370     return inScopeCommon<isScopeMarker>(m_top.get(), targetTag);
371 }
372
373 bool HTMLElementStack::inScope(const QualifiedName& tagName) const
374 {
375     // FIXME: Is localName() right for non-html elements?
376     return inScope(tagName.localName());
377 }
378
379 bool HTMLElementStack::inListItemScope(const AtomicString& targetTag) const
380 {
381     return inScopeCommon<isListItemScopeMarker>(m_top.get(), targetTag);
382 }
383
384 bool HTMLElementStack::inListItemScope(const QualifiedName& tagName) const
385 {
386     // FIXME: Is localName() right for non-html elements?
387     return inListItemScope(tagName.localName());
388 }
389
390 bool HTMLElementStack::inTableScope(const AtomicString& targetTag) const
391 {
392     return inScopeCommon<isTableScopeMarker>(m_top.get(), targetTag);
393 }
394
395 bool HTMLElementStack::inTableScope(const QualifiedName& tagName) const
396 {
397     // FIXME: Is localName() right for non-html elements?
398     return inTableScope(tagName.localName());
399 }
400
401 Element* HTMLElementStack::htmlElement() const
402 {
403     ASSERT(m_htmlElement);
404     return m_htmlElement;
405 }
406
407 Element* HTMLElementStack::headElement() const
408 {
409     ASSERT(m_headElement);
410     return m_headElement;
411 }
412
413 Element* HTMLElementStack::bodyElement() const
414 {
415     ASSERT(m_bodyElement);
416     return m_bodyElement;
417 }
418
419 void HTMLElementStack::pushCommon(PassRefPtr<Element> element)
420 {
421     ASSERT(m_htmlElement);
422     m_top.set(new ElementRecord(element, m_top.release()));
423     top()->beginParsingChildren();
424 }
425
426 void HTMLElementStack::popCommon()
427 {
428     ASSERT(!top()->hasTagName(HTMLNames::htmlTag));
429     ASSERT(!top()->hasTagName(HTMLNames::headTag) || !m_headElement);
430     ASSERT(!top()->hasTagName(HTMLNames::bodyTag) || !m_bodyElement);
431     top()->finishParsingChildren();
432     m_top = m_top->releaseNext();
433 }
434
435 void HTMLElementStack::removeNonTopCommon(Element* element)
436 {
437     ASSERT(!element->hasTagName(HTMLNames::htmlTag));
438     ASSERT(!element->hasTagName(HTMLNames::bodyTag));
439     ASSERT(top() != element);
440     for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
441         if (pos->next()->element() == element) {
442             // FIXME: Is it OK to call finishParsingChildren()
443             // when the children aren't actually finished?
444             element->finishParsingChildren();
445             pos->setNext(pos->next()->releaseNext());
446             return;
447         }
448     }
449     ASSERT_NOT_REACHED();
450 }
451
452 #ifndef NDEBUG
453
454 void HTMLElementStack::show()
455 {
456     for (ElementRecord* record = m_top.get(); record; record = record->next())
457         record->element()->showNode();
458 }
459
460 #endif
461
462 }