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