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