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