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()
41{
42}
43
44HTMLFormattingElementList::~HTMLFormattingElementList()
45{
46}
47
48Element* 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 0;
54        if (entry.stackItem()->matchesHTMLTag(targetName))
55            return entry.element();
56    }
57    return 0;
58}
59
60bool HTMLFormattingElementList::contains(Element* element)
61{
62    return !!find(element);
63}
64
65HTMLFormattingElementList::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
75HTMLFormattingElementList::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
82void 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
97void HTMLFormattingElementList::append(PassRefPtr<HTMLStackItem> item)
98{
99    ensureNoahsArkCondition(item.get());
100    m_entries.append(item);
101}
102
103void HTMLFormattingElementList::remove(Element* element)
104{
105    size_t index = m_entries.reverseFind(element);
106    if (index != notFound)
107        m_entries.remove(index);
108}
109
110void HTMLFormattingElementList::appendMarker()
111{
112    m_entries.append(Entry::MarkerEntry);
113}
114
115void 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
126void 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().get();
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
161void 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            Attribute* candidateAttribute = candidate->getAttributeItem(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
205void 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}
219