Home | History | Annotate | Download | only in parser 
      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 
     33 namespace 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.
     38 static const size_t kNoahsArkCapacity = 3;
     39 
     40 HTMLFormattingElementList::HTMLFormattingElementList()
     41 {
     42 }
     43 
     44 HTMLFormattingElementList::~HTMLFormattingElementList()
     45 {
     46 }
     47 
     48 Element* 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 
     60 bool HTMLFormattingElementList::contains(Element* element)
     61 {
     62     return !!find(element);
     63 }
     64 
     65 HTMLFormattingElementList::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 
     75 HTMLFormattingElementList::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 
     82 void 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 
     97 void HTMLFormattingElementList::append(PassRefPtrWillBeRawPtr<HTMLStackItem> item)
     98 {
     99     ensureNoahsArkCondition(item.get());
    100     m_entries.append(item);
    101 }
    102 
    103 void HTMLFormattingElementList::remove(Element* element)
    104 {
    105     size_t index = m_entries.reverseFind(element);
    106     if (index != kNotFound)
    107         m_entries.remove(index);
    108 }
    109 
    110 void HTMLFormattingElementList::appendMarker()
    111 {
    112     m_entries.append(Entry::MarkerEntry);
    113 }
    114 
    115 void 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 
    126 void 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 
    161 void 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 
    205 void 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