// 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/node_computed_style.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/html/forms/text_control_element.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 {
namespace {

// Returns true if the search should ignore the given |node|'s contents. In
// other words, we don't need to recurse into the node's children.
bool ShouldIgnoreContents(const Node& node) {
  if (node.getNodeType() == Node::kCommentNode) {
    return true;
  }

  const auto* element = DynamicTo<HTMLElement>(node);
  if (!element)
    return false;
  return (!element->ShouldSerializeEndTag() &&
          !IsA<HTMLInputElement>(*element)) ||
         (IsA<TextControlElement>(*element) &&
          !To<TextControlElement>(*element).SuggestedValue().IsEmpty()) ||
         IsA<HTMLIFrameElement>(*element) || IsA<HTMLImageElement>(*element) ||
         IsA<HTMLMeterElement>(*element) || IsA<HTMLObjectElement>(*element) ||
         IsA<HTMLProgressElement>(*element) ||
         (IsA<HTMLSelectElement>(*element) &&
          To<HTMLSelectElement>(*element).UsesMenuList()) ||
         IsA<HTMLStyleElement>(*element) || IsA<HTMLScriptElement>(*element) ||
         IsA<HTMLVideoElement>(*element) || IsA<HTMLAudioElement>(*element) ||
         (element->GetDisplayLockContext() &&
          element->GetDisplayLockContext()->IsLocked() &&
          !element->GetDisplayLockContext()->IsActivatable(
              DisplayLockActivationReason::kFindInPage));
}

// Returns the first ancestor that isn't searchable. In other words, either
// ShouldIgnoreContents() returns true for it or it has a display: none style.
// Returns nullptr if no such ancestor exists.
Node* GetNonSearchableAncestor(const Node& node) {
  for (Node& ancestor : FlatTreeTraversal::InclusiveAncestorsOf(node)) {
    const ComputedStyle* style = ancestor.EnsureComputedStyle();
    if (ancestor.IsDocumentNode())
      return nullptr;
    if ((style && style->Display() == EDisplay::kNone) ||
        ShouldIgnoreContents(ancestor))
      return &ancestor;
  }
  return nullptr;
}

// Returns the next/previous node after |start_node| (including start node) that
// is a text node and is searchable and visible.
template <class Direction>
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)
      return nullptr;
    node = Direction::NextSkippingSubtree(*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 = Direction::NextSkippingSubtree(*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 = Direction::Next(*node);
  }
  return nullptr;
}

// Returns true if the given |node| is considered a 'block' for find-in-page,
// scroll-to-text and link-to-text even though it might not have a separate
// LayoutBlockFlow. For example, input fields should be considered a block
// boundary.
bool IsExplicitFindBoundary(const Node& node) {
  return IsTextControl(node);
}

// Checks if |start| appears before |end| in flat-tree order.
bool AreInOrder(const Node& start, const Node& end) {
  const Node* node = &start;
  while (node && !node->isSameNode(&end)) {
    node = FlatTreeTraversal::Next(*node);
  }
  return node->isSameNode(&end);
}

}  // namespace

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

bool FindBuffer::IsInvalidMatch(MatchResultICU match) const {
  // Invalid matches are a result of accidentally matching elements that are
  // replaced with the max code point, and may lead to crashes. To avoid
  // crashing, we should skip the matches that are invalid - they would have
  // either an empty position or a non-offset-in-anchor position.
  const unsigned start_index = match.start;
  PositionInFlatTree start_position =
      PositionAtStartOfCharacterAtIndex(start_index);
  if (start_position.IsNull() || !start_position.IsOffsetInAnchor())
    return true;

  const unsigned end_index = match.start + match.length;
  DCHECK_LE(start_index, end_index);
  PositionInFlatTree end_position =
      PositionAtEndOfCharacterAtIndex(end_index - 1);
  if (end_position.IsNull() || !end_position.IsOffsetInAnchor())
    return true;
  return false;
}

EphemeralRangeInFlatTree FindBuffer::FindMatchInRange(
    const EphemeralRangeInFlatTree& range,
    String search_text,
    FindOptions options,
    base::Optional<base::TimeDelta> timeout_ms) {
  if (!range.StartPosition().IsConnected())
    return EphemeralRangeInFlatTree();

  base::TimeTicks start_time;

  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 (start_time.is_null()) {
      start_time = base::TimeTicks::Now();
    } else {
      auto time_elapsed = base::TimeTicks::Now() - start_time;
      if (timeout_ms.has_value() && time_elapsed > timeout_ms.value()) {
        return EphemeralRangeInFlatTree(
            PositionInFlatTree::FirstPositionInNode(*node),
            PositionInFlatTree::FirstPositionInNode(*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()));
    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;
}

const Node& FindBuffer::GetFirstBlockLevelAncestorInclusive(const Node& 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.
  if (!node.GetLayoutObject())
    return *node.GetDocument().documentElement();

  for (const Node& ancestor : FlatTreeTraversal::InclusiveAncestorsOf(node)) {
    if (!ancestor.GetLayoutObject())
      continue;
    if (!IsInSameUninterruptedBlock(ancestor, node))
      return ancestor;
  }

  return *node.GetDocument().documentElement();
}

bool FindBuffer::IsInSameUninterruptedBlock(const Node& start_node,
                                            const Node& end_node) {
  DCHECK(AreInOrder(start_node, end_node));
  DCHECK(start_node.GetLayoutObject());
  DCHECK(end_node.GetLayoutObject());

  if (start_node.isSameNode(&end_node))
    return true;

  if (IsExplicitFindBoundary(start_node) || IsExplicitFindBoundary(end_node))
    return false;

  LayoutBlockFlow& start_block_flow =
      *NGOffsetMapping::GetInlineFormattingContextOf(
          *start_node.GetLayoutObject());
  LayoutBlockFlow& end_block_flow =
      *NGOffsetMapping::GetInlineFormattingContextOf(
          *end_node.GetLayoutObject());
  if (start_block_flow != end_block_flow)
    return false;

  // It's possible that 2 nodes are in the same block flow but there is a node
  // in between that has a separate block flow. An example is an input field.
  for (const Node* node = &start_node; !node->isSameNode(&end_node);
       node = FlatTreeTraversal::Next(*node)) {
    const ComputedStyle* style = node->GetComputedStyle();
    if (ShouldIgnoreContents(*node) || !style ||
        style->Display() == EDisplay::kNone ||
        style->Visibility() != EVisibility::kVisible)
      continue;

    if (node->GetLayoutObject() &&
        *NGOffsetMapping::GetInlineFormattingContextOf(
            *node->GetLayoutObject()) != start_block_flow)
      return false;
  }

  return true;
}

Node* FindBuffer::ForwardVisibleTextNode(Node& start_node) {
  struct ForwardDirection {
    static Node* Next(const Node& node) {
      return FlatTreeTraversal::Next(node);
    }
    static Node* NextSkippingSubtree(const Node& node) {
      return FlatTreeTraversal::NextSkippingChildren(node);
    }
  };
  return GetVisibleTextNode<ForwardDirection>(start_node);
}

Node* FindBuffer::BackwardVisibleTextNode(Node& start_node) {
  struct BackwardDirection {
    static Node* Next(const Node& node) {
      return FlatTreeTraversal::Previous(node);
    }
    static Node* NextSkippingSubtree(const Node& node) {
      // Unlike |NextSkippingChildren|, |Previous| already skips given nodes
      // subtree.
      return FlatTreeTraversal::Previous(node);
    }
  };
  return GetVisibleTextNode<BackwardDirection>(start_node);
}

FindBuffer::Results FindBuffer::FindMatches(const WebString& search_text,
                                            const blink::FindOptions options) {
  // We should return empty result if it's impossible to get a match (buffer is
  // empty or too short), or when something went wrong in layout, in which case
  // |offset_mapping_| is null.
  if (buffer_.IsEmpty() || search_text.length() > buffer_.size() ||
      !offset_mapping_)
    return Results();
  String search_text_16_bit = search_text;
  search_text_16_bit.Ensure16Bit();
  FoldQuoteMarksAndSoftHyphens(search_text_16_bit);
  return Results(*this, &text_searcher_, buffer_, search_text_16_bit, options);
}

void FindBuffer::CollectTextUntilBlockBoundary(
    const EphemeralRangeInFlatTree& range) {
  // 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_|.
  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 =
      ForwardVisibleTextNode(*range.StartPosition().NodeAsRangeFirstNode());
  if (!node || !node->isConnected())
    return;

  const Node& block_ancestor = GetFirstBlockLevelAncestorInclusive(*node);
  const Node* just_after_block = FlatTreeTraversal::Next(
      FlatTreeTraversal::LastWithinOrSelf(block_ancestor));

  // 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".

  // Used for checking if we reached a new block.
  Node* last_added_text_node = nullptr;

  // We will also stop if we encountered/passed |end_node|.
  Node* end_node = range.EndPosition().NodeAsRangeLastNode();

  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 (IsA<HTMLElement>(*node) &&
          !IsA<HTMLWBRElement>(To<HTMLElement>(*node))) {
        buffer_.push_back(kMaxCodepoint);
      }
      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;
    }

    if (style->Visibility() == EVisibility::kVisible &&
        node->GetLayoutObject()) {
      // This node is in its own sub-block separate from our starting position.
      if (last_added_text_node && last_added_text_node->GetLayoutObject() &&
          !IsInSameUninterruptedBlock(*last_added_text_node, *node))
        break;

      const auto* text_node = DynamicTo<Text>(node);
      if (text_node) {
        last_added_text_node = node;
        LayoutBlockFlow& block_flow =
            *NGOffsetMapping::GetInlineFormattingContextOf(
                *text_node->GetLayoutObject());
        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);
}

const 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;
      });
  if (it == buffer_node_mappings_.begin())
    return nullptr;
  auto* entry = std::prev(it);
  return entry;
}

PositionInFlatTree FindBuffer::PositionAtStartOfCharacterAtIndex(
    unsigned index) const {
  DCHECK_LT(index, buffer_.size());
  DCHECK(offset_mapping_);
  const BufferNodeMapping* entry = MappingForIndex(index);
  if (!entry)
    return PositionInFlatTree();
  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_);
  const BufferNodeMapping* entry = MappingForIndex(index);
  if (!entry)
    return PositionInFlatTree();
  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();
  }
}

// FindBuffer::Results implementation.
FindBuffer::Results::Results() {
  empty_result_ = true;
}

FindBuffer::Results::Results(const FindBuffer& find_buffer,
                             TextSearcherICU* text_searcher,
                             const Vector<UChar>& buffer,
                             const 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;
  find_buffer_ = &find_buffer;
  text_searcher_ = text_searcher;
  text_searcher_->SetPattern(search_text_, options);
  text_searcher_->SetText(buffer.data(), buffer.size());
  text_searcher_->SetOffset(0);
}

FindBuffer::Results::Iterator FindBuffer::Results::begin() const {
  if (empty_result_)
    return end();
  text_searcher_->SetOffset(0);
  return Iterator(*find_buffer_, text_searcher_, search_text_);
}

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

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

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

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

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

// Findbuffer::Results::Iterator implementation.
FindBuffer::Results::Iterator::Iterator(const FindBuffer& find_buffer,
                                        TextSearcherICU* text_searcher,
                                        const String& search_text)
    : find_buffer_(&find_buffer),
      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_);
  if (has_match_ && find_buffer_ && find_buffer_->IsInvalidMatch(match_))
    operator++();
}

}  // namespace blink