Use the original token to create an element in "reconstruct the active formatting...
[WebKit-https.git] / Source / WebCore / html / parser / HTMLFormattingElementList.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 "HTMLFormattingElementList.h"
28
29 #include "Element.h"
30 #include "NotImplemented.h"
31
32 #ifndef NDEBUG
33 #include <stdio.h>
34 #endif
35
36 namespace WebCore {
37
38 // Biblically, Noah's Ark only had room for two of each animal, but in the
39 // Book of Hixie (aka http://www.whatwg.org/specs/web-apps/current-work/multipage/parsing.html#list-of-active-formatting-elements),
40 // Noah's Ark of Formatting Elements can fit three of each element.
41 static const size_t kNoahsArkCapacity = 3;
42
43 static inline size_t attributeCountWithoutUpdate(Element* element)
44 {
45     return element->hasAttributesWithoutUpdate() ? element->attributeCount() : 0;
46 }
47
48 HTMLFormattingElementList::HTMLFormattingElementList()
49 {
50 }
51
52 HTMLFormattingElementList::~HTMLFormattingElementList()
53 {
54 }
55
56 Element* HTMLFormattingElementList::closestElementInScopeWithName(const AtomicString& targetName)
57 {
58     for (unsigned i = 1; i <= m_entries.size(); ++i) {
59         const Entry& entry = m_entries[m_entries.size() - i];
60         if (entry.isMarker())
61             return 0;
62         if (entry.element()->hasLocalName(targetName))
63             return entry.element();
64     }
65     return 0;
66 }
67
68 bool HTMLFormattingElementList::contains(Element* element)
69 {
70     return !!find(element);
71 }
72
73 HTMLFormattingElementList::Entry* HTMLFormattingElementList::find(Element* element)
74 {
75     size_t index = m_entries.reverseFind(element);
76     if (index != notFound) {
77         // This is somewhat of a hack, and is why this method can't be const.
78         return &m_entries[index];
79     }
80     return 0;
81 }
82
83 HTMLFormattingElementList::Bookmark HTMLFormattingElementList::bookmarkFor(Element* element)
84 {
85     size_t index = m_entries.reverseFind(element);
86     ASSERT(index != notFound);
87     return Bookmark(&at(index));
88 }
89
90 void HTMLFormattingElementList::swapTo(Element* oldElement, PassRefPtr<HTMLStackItem> newItem, const Bookmark& bookmark)
91 {
92     ASSERT(contains(oldElement));
93     ASSERT(!contains(newItem->element()));
94     if (!bookmark.hasBeenMoved()) {
95         ASSERT(bookmark.mark()->element() == oldElement);
96         bookmark.mark()->replaceElement(newItem);
97         return;
98     }
99     size_t index = bookmark.mark() - first();
100     ASSERT(index < size());
101     m_entries.insert(index + 1, newItem);
102     remove(oldElement);
103 }
104
105 void HTMLFormattingElementList::append(PassRefPtr<HTMLStackItem> item)
106 {
107     ensureNoahsArkCondition(item->element());
108     m_entries.append(item);
109 }
110
111 void HTMLFormattingElementList::remove(Element* element)
112 {
113     size_t index = m_entries.reverseFind(element);
114     if (index != notFound)
115         m_entries.remove(index);
116 }
117
118 void HTMLFormattingElementList::appendMarker()
119 {
120     m_entries.append(Entry::MarkerEntry);
121 }
122
123 void HTMLFormattingElementList::clearToLastMarker()
124 {
125     // http://www.whatwg.org/specs/web-apps/current-work/multipage/parsing.html#clear-the-list-of-active-formatting-elements-up-to-the-last-marker
126     while (m_entries.size()) {
127         bool shouldStop = m_entries.last().isMarker();
128         m_entries.removeLast();
129         if (shouldStop)
130             break;
131     }
132 }
133
134 void HTMLFormattingElementList::tryToEnsureNoahsArkConditionQuickly(Element* newElement, Vector<Element*>& remainingCandidates)
135 {
136     ASSERT(remainingCandidates.isEmpty());
137
138     if (m_entries.size() < kNoahsArkCapacity)
139         return;
140
141     // Use a vector with inline capacity to avoid a malloc in the common case
142     // of a quickly ensuring the condition.
143     Vector<Element*, 10> candidates;
144
145     size_t newElementAttributeCount = attributeCountWithoutUpdate(newElement);
146
147     for (size_t i = m_entries.size(); i; ) {
148         --i;
149         Entry& entry = m_entries[i];
150         if (entry.isMarker())
151             break;
152
153         // Quickly reject obviously non-matching candidates.
154         Element* candidate = entry.element();
155         if (newElement->tagQName() != candidate->tagQName())
156             continue;
157         if (attributeCountWithoutUpdate(candidate) != newElementAttributeCount)
158             continue;
159
160         candidates.append(candidate);
161     }
162
163     if (candidates.size() < kNoahsArkCapacity)
164         return; // There's room for the new element in the ark. There's no need to copy out the remainingCandidates.
165
166     remainingCandidates.append(candidates);
167 }
168
169 void HTMLFormattingElementList::ensureNoahsArkCondition(Element* newElement)
170 {
171     Vector<Element*> candidates;
172     tryToEnsureNoahsArkConditionQuickly(newElement, candidates);
173     if (candidates.isEmpty())
174         return;
175
176     // We pre-allocate and re-use this second vector to save one malloc per
177     // attribute that we verify.
178     Vector<Element*> remainingCandidates;
179     remainingCandidates.reserveInitialCapacity(candidates.size());
180
181     size_t newElementAttributeCount = attributeCountWithoutUpdate(newElement);
182
183     for (size_t i = 0; i < newElementAttributeCount; ++i) {
184         Attribute* attribute = newElement->attributeItem(i);
185
186         for (size_t j = 0; j < candidates.size(); ++j) {
187             Element* candidate = candidates[j];
188
189             // These properties should already have been checked by tryToEnsureNoahsArkConditionQuickly.
190             ASSERT(newElement->attributeCount() == candidate->attributeCount());
191             ASSERT(newElement->tagQName() == candidate->tagQName());
192
193             // FIXME: Technically we shouldn't read this information back from
194             // the DOM. Instead, the parser should keep a copy of the information.
195             // This isn't really much of a problem for our implementation because
196             // we run the parser on the main thread, but the spec is written so
197             // that implementations can run off the main thread. If JavaScript
198             // changes the attributes values, we could get a slightly wrong
199             // output here.
200             if (candidate->fastGetAttribute(attribute->name()) == attribute->value())
201                 remainingCandidates.append(candidate);
202         }
203
204         if (remainingCandidates.size() < kNoahsArkCapacity)
205             return;
206
207         candidates.swap(remainingCandidates);
208         remainingCandidates.shrink(0);
209     }
210
211     // Inductively, we shouldn't spin this loop very many times. It's possible,
212     // however, that we wil spin the loop more than once because of how the
213     // formatting element list gets permuted.
214     for (size_t i = kNoahsArkCapacity - 1; i < candidates.size(); ++i)
215         remove(candidates[i]);
216 }
217
218 #ifndef NDEBUG
219
220 void HTMLFormattingElementList::show()
221 {
222     for (unsigned i = 1; i <= m_entries.size(); ++i) {
223         const Entry& entry = m_entries[m_entries.size() - i];
224         if (entry.isMarker())
225             fprintf(stderr, "marker\n");
226         else
227             entry.element()->showNode();
228     }
229 }
230
231 #endif
232
233 }