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 "core/html/parser/HTMLFormattingElementList.h" 28 29#ifndef NDEBUG 30#include <stdio.h> 31#endif 32 33namespace blink { 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 != kNotFound) { 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 != kNotFound); 79 return Bookmark(&at(index)); 80} 81 82void HTMLFormattingElementList::swapTo(Element* oldElement, PassRefPtrWillBeRawPtr<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(PassRefPtrWillBeRawPtr<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 != kNotFound) 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, WillBeHeapVector<RawPtrWillBeMember<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 WillBeHeapVector<RawPtrWillBeMember<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 WillBeHeapVector<RawPtrWillBeMember<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 WillBeHeapVector<RawPtrWillBeMember<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