third_party/blink/renderer/core/editing/finder/find_buffer.cc

// Copyright 2018 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "third_party/blink/renderer/core/editing/finder/find_buffer.h"

#include "third_party/blink/renderer/core/css/style_change_reason.h"
#include "third_party/blink/renderer/core/dom/document.h"
#include "third_party/blink/renderer/core/dom/range.h"
#include "third_party/blink/renderer/core/dom/text.h"
#include "third_party/blink/renderer/core/editing/editing_utilities.h"
#include "third_party/blink/renderer/core/editing/ephemeral_range.h"
#include "third_party/blink/renderer/core/editing/iterators/text_searcher_icu.h"
#include "third_party/blink/renderer/core/html/forms/html_form_control_element.h"
#include "third_party/blink/renderer/core/html/forms/html_select_element.h"
#include "third_party/blink/renderer/core/invisible_dom/invisible_dom.h"
#include "third_party/blink/renderer/core/layout/layout_block_flow.h"
#include "third_party/blink/renderer/core/layout/layout_object.h"
#include "third_party/blink/renderer/core/layout/ng/inline/ng_inline_node.h"
#include "third_party/blink/renderer/core/layout/ng/inline/ng_offset_mapping.h"
#include "third_party/blink/renderer/core/style/computed_style.h"
#include "third_party/blink/renderer/platform/text/unicode_utilities.h"
#include "third_party/blink/renderer/platform/wtf/text/character_names.h"
#include "third_party/blink/renderer/platform/wtf/text/unicode.h"

namespace blink {

FindBuffer::FindBuffer(const EphemeralRangeInFlatTree& range) {
  DCHECK(range.IsNotNull() && !range.IsCollapsed()) << range;
  CollectTextUntilBlockBoundary(range);
}

FindBuffer::Results::Results() {
  empty_result_ = true;
}

FindBuffer::Results::Results(const Vector<UChar>& buffer,
                             String search_text,
                             const blink::FindOptions options) {
  // We need to own the |search_text| because |text_searcher_| only has a
  // StringView (doesn't own the search text).
  search_text_ = search_text;
  text_searcher_.SetPattern(search_text_, options);
  text_searcher_.SetText(buffer.data(), buffer.size());
  text_searcher_.SetOffset(0);
}

FindBuffer::Results::Iterator::Iterator(TextSearcherICU* text_searcher,
                                        String search_text)
    : text_searcher_(text_searcher), has_match_(true) {
  operator++();
}

const FindBuffer::BufferMatchResult FindBuffer::Results::Iterator::operator*()
    const {
  DCHECK(has_match_);
  return FindBuffer::BufferMatchResult({match_.start, match_.length});
}

void FindBuffer::Results::Iterator::operator++() {
  DCHECK(has_match_);
  has_match_ = text_searcher_->NextMatchResult(match_);
}

FindBuffer::Results::Iterator FindBuffer::Results::begin() {
  if (empty_result_)
    return end();
  text_searcher_.SetOffset(0);
  return Iterator(&text_searcher_, search_text_);
}

FindBuffer::Results::Iterator FindBuffer::Results::end() const {
  return Iterator();
}

bool FindBuffer::Results::IsEmpty() {
  return begin() == end();
}

FindBuffer::BufferMatchResult FindBuffer::Results::front() {
  return *begin();
}

FindBuffer::BufferMatchResult FindBuffer::Results::back() {
  Iterator last_result;
  for (Iterator it = begin(); it != end(); ++it) {
    last_result = it;
  }
  return *last_result;
}

unsigned FindBuffer::Results::CountForTesting() {
  unsigned result = 0;
  for (Iterator it = begin(); it != end(); ++it) {
    ++result;
  }
  return result;
}

bool ShouldIgnoreContents(const Node& node) {
  const auto* element = DynamicTo<HTMLElement>(node);
  if (!element)
    return false;
  return (!element->ShouldSerializeEndTag() && !IsHTMLInputElement(*element)) ||
         IsA<HTMLIFrameElement>(*element) || IsHTMLImageElement(*element) ||
         IsA<HTMLLegendElement>(*element) || IsA<HTMLMeterElement>(*element) ||
         IsHTMLObjectElement(*element) || IsA<HTMLProgressElement>(*element) ||
         (IsA<HTMLSelectElement>(*element) &&
          To<HTMLSelectElement>(*element).UsesMenuList()) ||
         IsA<HTMLStyleElement>(*element) || IsA<HTMLScriptElement>(*element) ||
         IsHTMLVideoElement(*element) || IsA<HTMLAudioElement>(*element) ||
         (element->GetDisplayLockContext() &&
          !element->GetDisplayLockContext()->IsActivatable(
              DisplayLockActivationReason::kFindInPage));
}

Node* GetNonSearchableAncestor(const Node& node) {
  for (Node& ancestor : FlatTreeTraversal::InclusiveAncestorsOf(node)) {
    const ComputedStyle* style = ancestor.EnsureComputedStyle();
    if ((style && style->Display() == EDisplay::kNone) ||
        ShouldIgnoreContents(ancestor))
      return &ancestor;
    if (ancestor.IsDocumentNode())
      return nullptr;
  }
  return nullptr;
}

bool IsBlock(EDisplay display) {
  return display == EDisplay::kBlock || display == EDisplay::kTable ||
         display == EDisplay::kFlowRoot || display == EDisplay::kGrid ||
         display == EDisplay::kFlex || display == EDisplay::kListItem;
}

Node* GetVisibleTextNode(Node& start_node) {
  Node* node = &start_node;
  // Move to outside display none subtree if we're inside one.
  while (Node* ancestor = GetNonSearchableAncestor(*node)) {
    if (ancestor->IsDocumentNode())
      return nullptr;
    node = FlatTreeTraversal::NextSkippingChildren(*ancestor);
    if (!node)
      return nullptr;
  }
  // Move to first text node that's visible.
  while (node) {
    const ComputedStyle* style = node->EnsureComputedStyle();
    if (ShouldIgnoreContents(*node) ||
        (style && style->Display() == EDisplay::kNone)) {
      // This element and its descendants are not visible, skip it.
      node = FlatTreeTraversal::NextSkippingChildren(*node);
      continue;
    }
    if (style && style->Visibility() == EVisibility::kVisible &&
        node->IsTextNode()) {
      return node;
    }
    // This element is hidden, but node might be visible,
    // or this is not a text node, so we move on.
    node = FlatTreeTraversal::Next(*node);
  }
  return nullptr;
}

Node& GetLowestDisplayBlockInclusiveAncestor(const Node& start_node) {
  // Gets lowest inclusive ancestor that has block display value.
  // <div id=outer>a<div id=inner>b</div>c</div>
  // If we run this on "a" or "c" text node in we will get the outer div.
  // If we run it on the "b" text node we will get the inner div.
  for (Node& ancestor : FlatTreeTraversal::InclusiveAncestorsOf(start_node)) {
    const ComputedStyle* style = ancestor.EnsureComputedStyle();
    if (style && !ancestor.IsTextNode() && IsBlock(style->Display()))
      return ancestor;
  }
  return *start_node.GetDocument().documentElement();
}

EphemeralRangeInFlatTree FindBuffer::FindMatchInRange(
    const EphemeralRangeInFlatTree& range,
    String search_text,
    FindOptions options) {
  if (!range.StartPosition().IsConnected())
    return EphemeralRangeInFlatTree();

  EphemeralRangeInFlatTree last_match_range;
  Node* first_node = range.StartPosition().NodeAsRangeFirstNode();
  Node* past_last_node = range.EndPosition().NodeAsRangePastLastNode();
  Node* node = first_node;
  while (node && node != past_last_node) {
    if (GetNonSearchableAncestor(*node)) {
      node = FlatTreeTraversal::NextSkippingChildren(*node);
      continue;
    }
    if (!node->IsTextNode()) {
      node = FlatTreeTraversal::Next(*node);
      continue;
    }
    // If we're in the same node as the start position, start from the start
    // position instead of the start of this node.
    PositionInFlatTree start_position =
        node == first_node ? range.StartPosition()
                           : PositionInFlatTree::FirstPositionInNode(*node);
    if (start_position >= range.EndPosition())
      break;

    FindBuffer buffer(
        EphemeralRangeInFlatTree(start_position, range.EndPosition()));
    std::unique_ptr<Results> match_results =
        buffer.FindMatches(search_text, options);
    if (!match_results->IsEmpty()) {
      if (!(options & kBackwards)) {
        BufferMatchResult match = match_results->front();
        return buffer.RangeFromBufferIndex(match.start,
                                           match.start + match.length);
      }
      BufferMatchResult match = match_results->back();
      last_match_range =
          buffer.RangeFromBufferIndex(match.start, match.start + match.length);
    }
    node = buffer.PositionAfterBlock().ComputeContainerNode();
  }
  return last_match_range;
}

std::unique_ptr<FindBuffer::Results> FindBuffer::FindMatches(
    const WebString& search_text,
    const blink::FindOptions options) const {
  if (buffer_.IsEmpty() || search_text.length() > buffer_.size())
    return std::make_unique<Results>();
  String search_text_16_bit = search_text;
  search_text_16_bit.Ensure16Bit();
  FoldQuoteMarksAndSoftHyphens(search_text_16_bit);
  return std::make_unique<Results>(buffer_, search_text_16_bit, options);
}

bool FindBuffer::PushScopedForcedUpdateIfNeeded(const Element& element) {
  if (auto* context = element.GetDisplayLockContext()) {
    DCHECK(context->IsActivatable(DisplayLockActivationReason::kFindInPage));
    scoped_forced_update_list_.push_back(context->GetScopedForcedUpdate());
    return true;
  }
  return false;
}

void FindBuffer::CollectScopedForcedUpdates(Node& start_node,
                                            const Node* search_range_end_node,
                                            const Node* node_after_block) {
  if (!RuntimeEnabledFeatures::DisplayLockingEnabled(
          start_node.GetExecutionContext()))
    return;
  if (start_node.GetDocument().LockedDisplayLockCount() ==
      start_node.GetDocument().ActivationBlockingDisplayLockCount())
    return;

  Node* node = &start_node;
  // We assume |start_node| is always visible/activatable if locked, so we don't
  // need to check activatability of ancestors here.
  for (Node& ancestor : FlatTreeTraversal::InclusiveAncestorsOf(*node)) {
    auto* ancestor_element = DynamicTo<Element>(ancestor);
    if (!ancestor_element)
      continue;
    PushScopedForcedUpdateIfNeeded(*ancestor_element);
  }

  while (node && node != node_after_block && node != search_range_end_node) {
    if (ShouldIgnoreContents(*node)) {
      // Will skip display:none/non-activatable locked subtrees/etc.
      node = FlatTreeTraversal::NextSkippingChildren(*node);
      continue;
    }
    if (auto* element = DynamicTo<Element>(node))
      PushScopedForcedUpdateIfNeeded(*element);
    node = FlatTreeTraversal::Next(*node);
  }
}

// Collects text until block boundary located at or after |start_node|
// to |buffer_|. Saves the next starting node after the block to
// |node_after_block_|.
void FindBuffer::CollectTextUntilBlockBoundary(
    const EphemeralRangeInFlatTree& range) {
  DCHECK(range.IsNotNull() && !range.IsCollapsed()) << range;

  node_after_block_ = nullptr;
  const Node* const first_node = range.StartPosition().NodeAsRangeFirstNode();
  if (!first_node)
    return;
  // Get first visible text node from |start_position|.
  Node* node =
      GetVisibleTextNode(*range.StartPosition().NodeAsRangeFirstNode());
  if (!node || !node->isConnected())
    return;

  Node& block_ancestor = GetLowestDisplayBlockInclusiveAncestor(*node);
  const Node* just_after_block = FlatTreeTraversal::Next(
      FlatTreeTraversal::LastWithinOrSelf(block_ancestor));
  const LayoutBlockFlow* last_block_flow = nullptr;

  // Collect all text under |block_ancestor| to |buffer_|,
  // unless we meet another block on the way. If so, we should split.
  // Example: <div id="outer">a<span>b</span>c<div>d</div></div>
  // Will try to collect all text in outer div but will actually
  // stop when it encounters the inner div. So buffer will be "abc".
  Node* const first_traversed_node = node;
  // We will also stop if we encountered/passed |end_node|.
  Node* end_node = range.EndPosition().NodeAsRangeLastNode();

  if (node) {
    CollectScopedForcedUpdates(*node, end_node, just_after_block);
    if (!scoped_forced_update_list_.IsEmpty())
      node->GetDocument().UpdateStyleAndLayout();
  }

  while (node && node != just_after_block) {
    if (ShouldIgnoreContents(*node)) {
      if (end_node && (end_node == node ||
                       FlatTreeTraversal::IsDescendantOf(*end_node, *node))) {
        // For setting |node_after_block| later.
        node = FlatTreeTraversal::NextSkippingChildren(*node);
        break;
      }
      // Move the node so we wouldn't encounter this node or its descendants
      // later.
      if (!IsHTMLWBRElement(To<HTMLElement>(*node)))
        buffer_.push_back(kObjectReplacementCharacter);
      node = FlatTreeTraversal::NextSkippingChildren(*node);
      continue;
    }
    const ComputedStyle* style = node->EnsureComputedStyle();
    if (style->Display() == EDisplay::kNone) {
      // This element and its descendants are not visible, skip it.
      // We can safely just check the computed style of this node since
      // we guarantee |block_ancestor| is visible.
      if (end_node && (end_node == node ||
                       FlatTreeTraversal::IsDescendantOf(*end_node, *node))) {
        // For setting |node_after_block| later.
        node = FlatTreeTraversal::NextSkippingChildren(*node);
        break;
      }
      node = FlatTreeTraversal::NextSkippingChildren(*node);
      if (node && !FlatTreeTraversal::IsDescendantOf(*node, block_ancestor))
        break;
      continue;
    }
    // This node is in its own sub-block separate from our starting position.
    const auto* text_node = DynamicTo<Text>(node);
    if (first_traversed_node != node && !text_node &&
        IsBlock(style->Display())) {
      break;
    }

    if (style->Visibility() == EVisibility::kVisible && text_node &&
        node->GetLayoutObject()) {
      LayoutBlockFlow& block_flow =
          *NGOffsetMapping::GetInlineFormattingContextOf(
              *text_node->GetLayoutObject());
      if (last_block_flow && last_block_flow != block_flow) {
        // We enter another block flow.
        break;
      }
      if (!last_block_flow) {
        last_block_flow = &block_flow;
      }
      AddTextToBuffer(*text_node, block_flow, range);
    }
    if (node == end_node) {
      node = FlatTreeTraversal::Next(*node);
      break;
    }
    node = FlatTreeTraversal::Next(*node);
  }
  node_after_block_ = node;
  FoldQuoteMarksAndSoftHyphens(buffer_.data(), buffer_.size());
}

EphemeralRangeInFlatTree FindBuffer::RangeFromBufferIndex(
    unsigned start_index,
    unsigned end_index) const {
  DCHECK_LE(start_index, end_index);
  PositionInFlatTree start_position =
      PositionAtStartOfCharacterAtIndex(start_index);
  PositionInFlatTree end_position =
      PositionAtEndOfCharacterAtIndex(end_index - 1);
  return EphemeralRangeInFlatTree(start_position, end_position);
}

FindBuffer::BufferNodeMapping FindBuffer::MappingForIndex(
    unsigned index) const {
  // Get the first entry that starts at a position higher than offset, and
  // move back one entry.
  auto* it = std::upper_bound(
      buffer_node_mappings_.begin(), buffer_node_mappings_.end(), index,
      [](const unsigned offset, const BufferNodeMapping& entry) {
        return offset < entry.offset_in_buffer;
      });
  DCHECK_NE(it, buffer_node_mappings_.begin());
  auto* const entry = std::prev(it);
  return *entry;
}

PositionInFlatTree FindBuffer::PositionAtStartOfCharacterAtIndex(
    unsigned index) const {
  DCHECK_LT(index, buffer_.size());
  DCHECK(offset_mapping_);
  BufferNodeMapping entry = MappingForIndex(index);
  return ToPositionInFlatTree(offset_mapping_->GetLastPosition(
      index - entry.offset_in_buffer + entry.offset_in_mapping));
}

PositionInFlatTree FindBuffer::PositionAtEndOfCharacterAtIndex(
    unsigned index) const {
  DCHECK_LT(index, buffer_.size());
  DCHECK(offset_mapping_);
  BufferNodeMapping entry = MappingForIndex(index);
  return ToPositionInFlatTree(offset_mapping_->GetFirstPosition(
      index - entry.offset_in_buffer + entry.offset_in_mapping + 1));
}

void FindBuffer::AddTextToBuffer(const Text& text_node,
                                 LayoutBlockFlow& block_flow,
                                 const EphemeralRangeInFlatTree& range) {
  if (!offset_mapping_) {
    offset_mapping_ = NGInlineNode::GetOffsetMapping(&block_flow);

    if (UNLIKELY(!offset_mapping_)) {
      // TODO(crbug.com/955678): There are certain cases where we fail to
      // compute // |NGOffsetMapping| due to failures in layout. As the root
      // cause is hard to fix at the moment, we work around it here so that the
      // production build doesn't crash.
      NOTREACHED();
      return;
    }
  }

  Position node_start =
      (&text_node == range.StartPosition().ComputeContainerNode())
          ? ToPositionInDOMTree(range.StartPosition().ToOffsetInAnchor())
          : Position::FirstPositionInNode(text_node);
  Position node_end =
      (&text_node == range.EndPosition().ComputeContainerNode())
          ? ToPositionInDOMTree(range.EndPosition().ToOffsetInAnchor())
          : Position::LastPositionInNode(text_node);
  unsigned last_unit_end = 0;
  bool first_unit = true;
  const String mapped_text = offset_mapping_->GetText();
  for (const NGOffsetMappingUnit& unit :
       offset_mapping_->GetMappingUnitsForDOMRange(
           EphemeralRange(node_start, node_end))) {
    if (first_unit || last_unit_end != unit.TextContentStart()) {
      // This is the first unit, or the units are not consecutive, so we need to
      // insert a new BufferNodeMapping.
      buffer_node_mappings_.push_back(
          BufferNodeMapping({buffer_.size(), unit.TextContentStart()}));
      first_unit = false;
    }
    String text_for_unit =
        mapped_text.Substring(unit.TextContentStart(),
                              unit.TextContentEnd() - unit.TextContentStart());
    text_for_unit.Ensure16Bit();
    buffer_.Append(text_for_unit.Characters16(), text_for_unit.length());
    last_unit_end = unit.TextContentEnd();
  }
}

}  // namespace blink