blob: 5cb2d8e045ea4edb17515750dae192ddff4e6bf5 [file] [log] [blame]
// 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/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/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;
}
void FindBuffer::InvisibleLayoutScope::EnsureRecalc(Node& block_root) {
if (did_recalc_)
return;
did_recalc_ = true;
DCHECK(block_root.GetDocument().Lifecycle().GetState() >=
DocumentLifecycle::kStyleClean);
if (InvisibleDOM::IsInsideInvisibleSubtree(block_root))
invisible_root_ = InvisibleDOM::InvisibleRoot(block_root);
else
invisible_root_ = &ToElement(block_root);
invisible_root_->GetDocument().SetFindInPageRoot(invisible_root_);
invisible_root_->SetNeedsStyleRecalc(
kSubtreeStyleChange,
StyleChangeReasonForTracing::Create(style_change_reason::kFindInvisible));
// TODO(rakina): This currently does layout too and might be expensive. In the
// future, we might to figure out a way to make NGOffsetMapping work with only
// style & layout tree so that we don't have to do layout here.
invisible_root_->GetDocument()
.UpdateStyleAndLayoutIgnorePendingStylesheetsConsideringInvisibleNodes();
}
FindBuffer::InvisibleLayoutScope::~InvisibleLayoutScope() {
if (!did_recalc_)
return;
invisible_root_->GetDocument().SetFindInPageRoot(nullptr);
invisible_root_->SetNeedsStyleRecalc(
kSubtreeStyleChange,
StyleChangeReasonForTracing::Create(style_change_reason::kFindInvisible));
invisible_root_->GetDocument().UpdateStyleAndLayoutIgnorePendingStylesheets();
}
bool ShouldIgnoreContents(const Node& node) {
if (!node.IsHTMLElement())
return false;
const HTMLElement& element = ToHTMLElement(node);
return (!element.ShouldSerializeEndTag() && !IsHTMLInputElement(element)) ||
IsHTMLIFrameElement(element) || IsHTMLImageElement(element) ||
IsHTMLLegendElement(element) || IsHTMLMeterElement(element) ||
IsHTMLObjectElement(element) || IsHTMLProgressElement(element) ||
IsHTMLSelectElement(element) || IsHTMLStyleElement(element) ||
IsHTMLScriptElement(element) || IsHTMLVideoElement(element) ||
IsHTMLAudioElement(element) ||
(element.GetDisplayLockContext() &&
!element.GetDisplayLockContext()->IsActivatable());
}
Node* GetNonSearchableAncestor(const Node& node) {
for (Node& ancestor : FlatTreeTraversal::InclusiveAncestorsOf(node)) {
const ComputedStyle* style = ancestor.EnsureComputedStyle();
if ((style && style->Display() == EDisplay::kNone) ||
ShouldIgnoreContents(node))
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);
}
// 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;
// Get first visible text node from |start_position|.
Node* node =
GetVisibleTextNode(*range.StartPosition().NodeAsRangeFirstNode());
if (!node || !node->isConnected()) {
node_after_block_ = nullptr;
return;
}
Node& block_ancestor = GetLowestDisplayBlockInclusiveAncestor(*node);
const Node* just_after_block = FlatTreeTraversal::Next(
FlatTreeTraversal::LastWithinOrSelf(block_ancestor));
const LayoutBlockFlow* last_block_flow = nullptr;
// Calculate layout tree and style for invisible nodes inside the whole
// subtree of |block_ancestor|.
if (node && InvisibleDOM::IsInsideInvisibleSubtree(*node))
invisible_layout_scope_.EnsureRecalc(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".
Node* const first_traversed_node = node;
// 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.
buffer_.push_back(kObjectReplacementCharacter);
node = FlatTreeTraversal::NextSkippingChildren(*node);
continue;
}
if (node->IsElementNode() && ToElement(node)->HasInvisibleAttribute() &&
!invisible_layout_scope_.DidRecalc()) {
// We found and invisible node. Calculate the layout & style for the whole
// block at once, and we need to recalculate the NGOffsetMapping and start
// from the beginning again because the layout tree had changed.
mapping_needs_recalc_ = true;
node = first_traversed_node;
last_block_flow = nullptr;
offset_mapping_storage_ = nullptr;
buffer_.clear();
invisible_layout_scope_.EnsureRecalc(block_ancestor);
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.
if (first_traversed_node != node && !node->IsTextNode() &&
IsBlock(style->Display())) {
break;
}
if (style->Visibility() == EVisibility::kVisible && node->IsTextNode() &&
node->GetLayoutObject()) {
const Text& text_node = ToText(*node);
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) {
DCHECK(!offset_mapping_storage_);
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());
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());
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_ || mapping_needs_recalc_) {
offset_mapping_ =
NGInlineNode::GetOffsetMapping(&block_flow, &offset_mapping_storage_);
mapping_needs_recalc_ = false;
}
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();
text_for_unit.Replace('\n', kObjectReplacementCharacter);
buffer_.Append(text_for_unit.Characters16(), text_for_unit.length());
last_unit_end = unit.TextContentEnd();
}
}
} // namespace blink