third_party/blink/renderer/core/html/parser/html_formatting_element_list.cc

/*
 * Copyright (C) 2010 Google, Inc. All Rights Reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY GOOGLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL GOOGLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "third_party/blink/renderer/core/html/parser/html_formatting_element_list.h"

#ifndef NDEBUG
#include <stdio.h>
#endif

namespace blink {

// Biblically, Noah's Ark only had room for two of each animal, but in the
// Book of Hixie (aka
// http://www.whatwg.org/specs/web-apps/current-work/multipage/parsing.html#list-of-active-formatting-elements),
// Noah's Ark of Formatting Elements can fit three of each element.
static const size_t kNoahsArkCapacity = 3;

HTMLFormattingElementList::HTMLFormattingElementList() = default;

HTMLFormattingElementList::~HTMLFormattingElementList() = default;

Element* HTMLFormattingElementList::ClosestElementInScopeWithName(
    const AtomicString& target_name) {
  for (wtf_size_t i = 1; i <= entries_.size(); ++i) {
    const Entry& entry = entries_[entries_.size() - i];
    if (entry.IsMarker())
      return nullptr;
    if (entry.StackItem()->MatchesHTMLTag(target_name))
      return entry.GetElement();
  }
  return nullptr;
}

bool HTMLFormattingElementList::Contains(Element* element) {
  return !!Find(element);
}

HTMLFormattingElementList::Entry* HTMLFormattingElementList::Find(
    Element* element) {
  wtf_size_t index = entries_.ReverseFind(element);
  if (index != kNotFound) {
    // This is somewhat of a hack, and is why this method can't be const.
    return &entries_[index];
  }
  return nullptr;
}

HTMLFormattingElementList::Bookmark HTMLFormattingElementList::BookmarkFor(
    Element* element) {
  wtf_size_t index = entries_.ReverseFind(element);
  DCHECK_NE(index, kNotFound);
  return Bookmark(&at(index));
}

void HTMLFormattingElementList::SwapTo(Element* old_element,
                                       HTMLStackItem* new_item,
                                       const Bookmark& bookmark) {
  DCHECK(Contains(old_element));
  DCHECK(!Contains(new_item->GetElement()));
  if (!bookmark.HasBeenMoved()) {
    DCHECK(bookmark.Mark()->GetElement() == old_element);
    bookmark.Mark()->ReplaceElement(new_item);
    return;
  }
  size_t index = bookmark.Mark() - First();
  SECURITY_DCHECK(index < size());
  entries_.insert(static_cast<wtf_size_t>(index + 1), new_item);
  Remove(old_element);
}

void HTMLFormattingElementList::Append(HTMLStackItem* item) {
  EnsureNoahsArkCondition(item);
  entries_.push_back(item);
}

void HTMLFormattingElementList::Remove(Element* element) {
  wtf_size_t index = entries_.ReverseFind(element);
  if (index != kNotFound)
    entries_.EraseAt(index);
}

void HTMLFormattingElementList::AppendMarker() {
  entries_.push_back(Entry::kMarkerEntry);
}

void HTMLFormattingElementList::ClearToLastMarker() {
  // http://www.whatwg.org/specs/web-apps/current-work/multipage/parsing.html#clear-the-list-of-active-formatting-elements-up-to-the-last-marker
  while (entries_.size()) {
    bool should_stop = entries_.back().IsMarker();
    entries_.pop_back();
    if (should_stop)
      break;
  }
}

void HTMLFormattingElementList::TryToEnsureNoahsArkConditionQuickly(
    HTMLStackItem* new_item,
    HeapVector<Member<HTMLStackItem>>& remaining_candidates) {
  DCHECK(remaining_candidates.IsEmpty());

  if (entries_.size() < kNoahsArkCapacity)
    return;

  // Use a vector with inline capacity to avoid a malloc in the common case of a
  // quickly ensuring the condition.
  HeapVector<Member<HTMLStackItem>, 10> candidates;

  wtf_size_t new_item_attribute_count = new_item->Attributes().size();

  for (wtf_size_t i = entries_.size(); i;) {
    --i;
    Entry& entry = entries_[i];
    if (entry.IsMarker())
      break;

    // Quickly reject obviously non-matching candidates.
    HTMLStackItem* candidate = entry.StackItem();
    if (new_item->LocalName() != candidate->LocalName() ||
        new_item->NamespaceURI() != candidate->NamespaceURI())
      continue;
    if (candidate->Attributes().size() != new_item_attribute_count)
      continue;

    candidates.push_back(candidate);
  }

  // There's room for the new element in the ark. There's no need to copy out
  // the remainingCandidates.
  if (candidates.size() < kNoahsArkCapacity)
    return;

  remaining_candidates.AppendVector(candidates);
}

void HTMLFormattingElementList::EnsureNoahsArkCondition(
    HTMLStackItem* new_item) {
  HeapVector<Member<HTMLStackItem>> candidates;
  TryToEnsureNoahsArkConditionQuickly(new_item, candidates);
  if (candidates.IsEmpty())
    return;

  // We pre-allocate and re-use this second vector to save one malloc per
  // attribute that we verify.
  HeapVector<Member<HTMLStackItem>> remaining_candidates;
  remaining_candidates.ReserveInitialCapacity(candidates.size());

  for (const auto& attribute : new_item->Attributes()) {
    for (const auto& candidate : candidates) {
      // These properties should already have been checked by
      // tryToEnsureNoahsArkConditionQuickly.
      DCHECK_EQ(new_item->Attributes().size(), candidate->Attributes().size());
      DCHECK_EQ(new_item->LocalName(), candidate->LocalName());
      DCHECK_EQ(new_item->NamespaceURI(), candidate->NamespaceURI());

      Attribute* candidate_attribute =
          candidate->GetAttributeItem(attribute.GetName());
      if (candidate_attribute &&
          candidate_attribute->Value() == attribute.Value())
        remaining_candidates.push_back(candidate);
    }

    if (remaining_candidates.size() < kNoahsArkCapacity)
      return;

    candidates.swap(remaining_candidates);
    remaining_candidates.Shrink(0);
  }

  // Inductively, we shouldn't spin this loop very many times. It's possible,
  // however, that we wil spin the loop more than once because of how the
  // formatting element list gets permuted.
  for (wtf_size_t i = kNoahsArkCapacity - 1; i < candidates.size(); ++i)
    Remove(candidates[i]->GetElement());
}

#ifndef NDEBUG

void HTMLFormattingElementList::Show() {
  for (wtf_size_t i = 1; i <= entries_.size(); ++i) {
    const Entry& entry = entries_[entries_.size() - i];
    if (entry.IsMarker())
      LOG(INFO) << "marker";
    else
      LOG(INFO) << *entry.GetElement();
  }
}

#endif

}  // namespace blink