15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2010 Google, Inc. All Rights Reserved. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modification, are permitted provided that the following conditions 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * are met: 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1. Redistributions of source code must retain the above copyright 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer. 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2. Redistributions in binary form must reproduce the above copyright 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer in the 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * documentation and/or other materials provided with the distribution. 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY GOOGLE INC. ``AS IS'' AND ANY 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GOOGLE INC. OR 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "config.h" 2753e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)#include "core/html/parser/HTMLFormattingElementList.h" 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include <stdio.h> 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 33c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)namespace blink { 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Biblically, Noah's Ark only had room for two of each animal, but in the 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Book of Hixie (aka http://www.whatwg.org/specs/web-apps/current-work/multipage/parsing.html#list-of-active-formatting-elements), 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Noah's Ark of Formatting Elements can fit three of each element. 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static const size_t kNoahsArkCapacity = 3; 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)HTMLFormattingElementList::HTMLFormattingElementList() 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)HTMLFormattingElementList::~HTMLFormattingElementList() 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Element* HTMLFormattingElementList::closestElementInScopeWithName(const AtomicString& targetName) 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (unsigned i = 1; i <= m_entries.size(); ++i) { 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const Entry& entry = m_entries[m_entries.size() - i]; 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (entry.isMarker()) 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 5453e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) if (entry.stackItem()->matchesHTMLTag(targetName)) 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return entry.element(); 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)bool HTMLFormattingElementList::contains(Element* element) 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return !!find(element); 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)HTMLFormattingElementList::Entry* HTMLFormattingElementList::find(Element* element) 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t index = m_entries.reverseFind(element); 6806f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) if (index != kNotFound) { 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This is somewhat of a hack, and is why this method can't be const. 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return &m_entries[index]; 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)HTMLFormattingElementList::Bookmark HTMLFormattingElementList::bookmarkFor(Element* element) 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t index = m_entries.reverseFind(element); 7806f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) ASSERT(index != kNotFound); 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return Bookmark(&at(index)); 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 82d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)void HTMLFormattingElementList::swapTo(Element* oldElement, PassRefPtrWillBeRawPtr<HTMLStackItem> newItem, const Bookmark& bookmark) 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(contains(oldElement)); 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!contains(newItem->element())); 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!bookmark.hasBeenMoved()) { 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(bookmark.mark()->element() == oldElement); 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bookmark.mark()->replaceElement(newItem); 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t index = bookmark.mark() - first(); 92926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) ASSERT_WITH_SECURITY_IMPLICATION(index < size()); 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_entries.insert(index + 1, newItem); 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) remove(oldElement); 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 97d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)void HTMLFormattingElementList::append(PassRefPtrWillBeRawPtr<HTMLStackItem> item) 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ensureNoahsArkCondition(item.get()); 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_entries.append(item); 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void HTMLFormattingElementList::remove(Element* element) 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t index = m_entries.reverseFind(element); 10606f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) if (index != kNotFound) 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_entries.remove(index); 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void HTMLFormattingElementList::appendMarker() 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_entries.append(Entry::MarkerEntry); 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void HTMLFormattingElementList::clearToLastMarker() 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // http://www.whatwg.org/specs/web-apps/current-work/multipage/parsing.html#clear-the-list-of-active-formatting-elements-up-to-the-last-marker 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (m_entries.size()) { 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool shouldStop = m_entries.last().isMarker(); 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_entries.removeLast(); 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (shouldStop) 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 126d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)void HTMLFormattingElementList::tryToEnsureNoahsArkConditionQuickly(HTMLStackItem* newItem, WillBeHeapVector<RawPtrWillBeMember<HTMLStackItem> >& remainingCandidates) 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(remainingCandidates.isEmpty()); 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_entries.size() < kNoahsArkCapacity) 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Use a vector with inline capacity to avoid a malloc in the common case 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // of a quickly ensuring the condition. 135d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) WillBeHeapVector<RawPtrWillBeMember<HTMLStackItem>, 10> candidates; 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 137926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) size_t newItemAttributeCount = newItem->attributes().size(); 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (size_t i = m_entries.size(); i; ) { 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) --i; 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Entry& entry = m_entries[i]; 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (entry.isMarker()) 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Quickly reject obviously non-matching candidates. 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HTMLStackItem* candidate = entry.stackItem().get(); 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (newItem->localName() != candidate->localName() || newItem->namespaceURI() != candidate->namespaceURI()) 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) continue; 149926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (candidate->attributes().size() != newItemAttributeCount) 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) continue; 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) candidates.append(candidate); 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (candidates.size() < kNoahsArkCapacity) 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; // There's room for the new element in the ark. There's no need to copy out the remainingCandidates. 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 158d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) remainingCandidates.appendVector(candidates); 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void HTMLFormattingElementList::ensureNoahsArkCondition(HTMLStackItem* newItem) 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 163d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) WillBeHeapVector<RawPtrWillBeMember<HTMLStackItem> > candidates; 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tryToEnsureNoahsArkConditionQuickly(newItem, candidates); 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (candidates.isEmpty()) 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We pre-allocate and re-use this second vector to save one malloc per 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // attribute that we verify. 170d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) WillBeHeapVector<RawPtrWillBeMember<HTMLStackItem> > remainingCandidates; 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) remainingCandidates.reserveInitialCapacity(candidates.size()); 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 173926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) const Vector<Attribute>& attributes = newItem->attributes(); 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (size_t i = 0; i < attributes.size(); ++i) { 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const Attribute& attribute = attributes[i]; 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (size_t j = 0; j < candidates.size(); ++j) { 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HTMLStackItem* candidate = candidates[j]; 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // These properties should already have been checked by tryToEnsureNoahsArkConditionQuickly. 181926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) ASSERT(newItem->attributes().size() == candidate->attributes().size()); 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(newItem->localName() == candidate->localName() && newItem->namespaceURI() == candidate->namespaceURI()); 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 184926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) Attribute* candidateAttribute = candidate->getAttributeItem(attribute.name()); 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (candidateAttribute && candidateAttribute->value() == attribute.value()) 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) remainingCandidates.append(candidate); 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (remainingCandidates.size() < kNoahsArkCapacity) 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) candidates.swap(remainingCandidates); 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) remainingCandidates.shrink(0); 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Inductively, we shouldn't spin this loop very many times. It's possible, 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // however, that we wil spin the loop more than once because of how the 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // formatting element list gets permuted. 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (size_t i = kNoahsArkCapacity - 1; i < candidates.size(); ++i) 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) remove(candidates[i]->element()); 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void HTMLFormattingElementList::show() 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (unsigned i = 1; i <= m_entries.size(); ++i) { 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const Entry& entry = m_entries[m_entries.size() - i]; 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (entry.isMarker()) 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) fprintf(stderr, "marker\n"); 2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) entry.element()->showNode(); 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 219