Use "= default" to denote default constructor or destructor
[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() = default;
41
42 HTMLFormattingElementList::~HTMLFormattingElementList() = default;
43
44 Element* 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
56 bool HTMLFormattingElementList::contains(Element& element)
57 {
58     return !!find(element);
59 }
60
61 auto 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
71 auto 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
78 void 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
93 void HTMLFormattingElementList::append(Ref<HTMLStackItem>&& item)
94 {
95     ensureNoahsArkCondition(item);
96     m_entries.append(WTFMove(item));
97 }
98
99 void HTMLFormattingElementList::remove(Element& element)
100 {
101     size_t index = m_entries.reverseFind(&element);
102     if (index != notFound)
103         m_entries.remove(index);
104 }
105
106 void HTMLFormattingElementList::appendMarker()
107 {
108     m_entries.append(Entry::MarkerEntry);
109 }
110
111 void 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
122 void 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
157 void 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
196 void 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 }