chromium/src/third_party/blink/renderer/core/layout/ng/inline/ng_offset_mapping.cc - manifest_repos/chromium_src - Git at Google

 // Copyright 2017 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/layout/ng/inline/ng_offset_mapping.h"

 #include <algorithm>
 #include "third_party/blink/renderer/core/dom/node.h"
 #include "third_party/blink/renderer/core/dom/node_computed_style.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/position.h"
 #include "third_party/blink/renderer/core/layout/layout_text_fragment.h"
 #include "third_party/blink/renderer/core/layout/ng/inline/ng_inline_node.h"
 #include "third_party/blink/renderer/core/layout/ng/ng_block_node.h"
 #include "third_party/blink/renderer/platform/text/character.h"

 namespace blink {

 namespace {

 // Note: LayoutFlowThread, used for multicol, can't provide offset mapping.
 bool CanUseNGOffsetMapping(const LayoutObject& object) {
   return object.IsLayoutBlockFlow() && !object.IsLayoutFlowThread();
 }

 Position CreatePositionForOffsetMapping(const Node& node, unsigned dom_offset) {
   if (auto* text_node = DynamicTo<Text>(node)) {
     // 'text-transform' may make the rendered text length longer than the
     // original text node, in which case we clamp the offset to avoid crashing.
     // TODO(crbug.com/750990): Support 'text-transform' to remove this hack.
 #if DCHECK_IS_ON()
     // Ensures that the clamping hack kicks in only with text-transform.
     if (node.ComputedStyleRef().TextTransform() == ETextTransform::kNone)
       DCHECK_LE(dom_offset, text_node->length());
 #endif
     const unsigned clamped_offset = std::min(dom_offset, text_node->length());
     return Position(&node, clamped_offset);
   }
   // For non-text-anchored position, the offset must be either 0 or 1.
   DCHECK_LE(dom_offset, 1u);
   return dom_offset ? Position::AfterNode(node) : Position::BeforeNode(node);
 }

 std::pair<const Node&, unsigned> ToNodeOffsetPair(const Position& position) {
   DCHECK(NGOffsetMapping::AcceptsPosition(position)) << position;
   if (auto* text_node = DynamicTo<Text>(position.AnchorNode())) {
     if (position.IsOffsetInAnchor())
       return {*position.AnchorNode(), position.OffsetInContainerNode()};
     if (position.IsBeforeAnchor())
       return {*position.AnchorNode(), 0};
     DCHECK(position.IsAfterAnchor());
     return {*position.AnchorNode(), text_node->length()};
   }
   if (position.IsBeforeAnchor())
     return {*position.AnchorNode(), 0};
   return {*position.AnchorNode(), 1};
 }

 // TODO(xiaochengh): Introduce predicates for comparing Position and
 // NGOffsetMappingUnit, to reduce position-offset conversion and ad-hoc
 // predicates below.

 }  // namespace

 LayoutBlockFlow* NGInlineFormattingContextOf(const Position& position) {
   if (!RuntimeEnabledFeatures::LayoutNGEnabled())
     return nullptr;
   LayoutBlockFlow* block_flow =
       NGOffsetMapping::GetInlineFormattingContextOf(position);
   if (!block_flow || !block_flow->IsLayoutNGMixin())
     return nullptr;
   return block_flow;
 }

 // static
 LayoutBlockFlow* NGOffsetMapping::GetInlineFormattingContextOf(
     const Position& position) {
   if (!AcceptsPosition(position))
     return nullptr;
   const auto node_offset_pair = ToNodeOffsetPair(position);
   const LayoutObject* layout_object =
       AssociatedLayoutObjectOf(node_offset_pair.first, node_offset_pair.second);
   if (!layout_object)
     return nullptr;
   return GetInlineFormattingContextOf(*layout_object);
 }

 NGOffsetMappingUnit::NGOffsetMappingUnit(NGOffsetMappingUnitType type,
                                          const LayoutObject& layout_object,
                                          unsigned dom_start,
                                          unsigned dom_end,
                                          unsigned text_content_start,
                                          unsigned text_content_end)
     : type_(type),
       layout_object_(&layout_object),
       dom_start_(dom_start),
       dom_end_(dom_end),
       text_content_start_(text_content_start),
       text_content_end_(text_content_end) {
   AssertValid();
 }

 void NGOffsetMappingUnit::AssertValid() const {
 #if ENABLE_SECURITY_ASSERT
   SECURITY_DCHECK(dom_start_ <= dom_end_) << dom_start_ << " vs. " << dom_end_;
   SECURITY_DCHECK(text_content_start_ <= text_content_end_)
       << text_content_start_ << " vs. " << text_content_end_;
   if (layout_object_->IsText() &&
       !To<LayoutText>(*layout_object_).IsWordBreak()) {
     const auto& layout_text = To<LayoutText>(*layout_object_);
     const unsigned text_start =
         AssociatedNode() ? layout_text.TextStartOffset() : 0;
     const unsigned text_end = text_start + layout_text.TextLength();
     SECURITY_DCHECK(dom_end_ >= text_start)
         << dom_end_ << " vs. " << text_start;
     SECURITY_DCHECK(dom_end_ <= text_end) << dom_end_ << " vs. " << text_end;
   } else {
     SECURITY_DCHECK(dom_start_ == 0) << dom_start_;
     SECURITY_DCHECK(dom_end_ == 1) << dom_end_;
   }
 #endif
 }

 const Node* NGOffsetMappingUnit::AssociatedNode() const {
   if (const auto* text_fragment = DynamicTo<LayoutTextFragment>(layout_object_))
     return text_fragment->AssociatedTextNode();
   return layout_object_->GetNode();
 }

 const Node& NGOffsetMappingUnit::GetOwner() const {
   const Node* const node = AssociatedNode();
   DCHECK(node) << layout_object_;
   return *node;
 }

 bool NGOffsetMappingUnit::Concatenate(const NGOffsetMappingUnit& other) {
   if (layout_object_ != other.layout_object_)
     return false;
   if (type_ != other.type_)
     return false;
   if (dom_end_ != other.dom_start_)
     return false;
   if (text_content_end_ != other.text_content_start_)
     return false;
   // Don't merge first letter and remaining text
   if (const auto* text_fragment =
           DynamicTo<LayoutTextFragment>(layout_object_)) {
     // TODO(layout-dev): Fix offset calculation for text-transform
     if (text_fragment->IsRemainingTextLayoutObject() &&
         other.dom_start_ == text_fragment->TextStartOffset())
       return false;
   }
   dom_end_ = other.dom_end_;
   text_content_end_ = other.text_content_end_;
   return true;
 }

 unsigned NGOffsetMappingUnit::ConvertDOMOffsetToTextContent(
     unsigned offset) const {
   DCHECK_GE(offset, dom_start_);
   DCHECK_LE(offset, dom_end_);
   // DOM start is always mapped to text content start.
   if (offset == dom_start_)
     return text_content_start_;
   // DOM end is always mapped to text content end.
   if (offset == dom_end_)
     return text_content_end_;
   // Handle collapsed mapping.
   if (text_content_start_ == text_content_end_)
     return text_content_start_;
   // Handle has identity mapping.
   return offset - dom_start_ + text_content_start_;
 }

 unsigned NGOffsetMappingUnit::ConvertTextContentToFirstDOMOffset(
     unsigned offset) const {
   DCHECK_GE(offset, text_content_start_);
   DCHECK_LE(offset, text_content_end_);
   // Always return DOM start for collapsed units.
   if (text_content_start_ == text_content_end_)
     return dom_start_;
   // Handle identity mapping.
   if (type_ == NGOffsetMappingUnitType::kIdentity)
     return dom_start_ + offset - text_content_start_;
   // Handle expanded mapping.
   return offset < text_content_end_ ? dom_start_ : dom_end_;
 }

 unsigned NGOffsetMappingUnit::ConvertTextContentToLastDOMOffset(
     unsigned offset) const {
   DCHECK_GE(offset, text_content_start_);
   DCHECK_LE(offset, text_content_end_);
   // Always return DOM end for collapsed units.
   if (text_content_start_ == text_content_end_)
     return dom_end_;
   // In a non-collapsed unit, mapping between DOM and text content offsets is
   // one-to-one. Reuse existing code.
   return ConvertTextContentToFirstDOMOffset(offset);
 }

 // static
 bool NGOffsetMapping::AcceptsPosition(const Position& position) {
   if (position.IsNull())
     return false;
   if (position.AnchorNode()->IsTextNode()) {
     // Position constructor should have rejected other anchor types.
     DCHECK(position.IsOffsetInAnchor() || position.IsBeforeAnchor() ||
            position.IsAfterAnchor());
     return true;
   }
   if (!position.IsBeforeAnchor() && !position.IsAfterAnchor())
     return false;
   const LayoutObject* layout_object = position.AnchorNode()->GetLayoutObject();
   if (!layout_object || !layout_object->IsInline())
     return false;
   return layout_object->IsText() || layout_object->IsAtomicInlineLevel();
 }

 // static
 const NGOffsetMapping* NGOffsetMapping::GetFor(const Position& position) {
   if (!RuntimeEnabledFeatures::LayoutNGEnabled())
     return nullptr;
   if (!NGOffsetMapping::AcceptsPosition(position))
     return nullptr;
   LayoutBlockFlow* context = NGInlineFormattingContextOf(position);
   if (!context)
     return nullptr;
   return NGInlineNode::GetOffsetMapping(context);
 }

 // static
 const NGOffsetMapping* NGOffsetMapping::GetFor(
     const LayoutObject* layout_object) {
   if (!RuntimeEnabledFeatures::LayoutNGEnabled())
     return nullptr;
   if (!layout_object)
     return nullptr;
   LayoutBlockFlow* context = layout_object->ContainingNGBlockFlow();
   if (!context)
     return nullptr;
   return NGInlineNode::GetOffsetMapping(context);
 }

 // static
 LayoutBlockFlow* NGOffsetMapping::GetInlineFormattingContextOf(
     const LayoutObject& object) {
   for (LayoutObject* runner = object.Parent(); runner;
        runner = runner->Parent()) {
     if (!CanUseNGOffsetMapping(*runner))
       continue;
     return To<LayoutBlockFlow>(runner);
   }
   return nullptr;
 }

 NGOffsetMapping::NGOffsetMapping(UnitVector&& units,
                                  RangeMap&& ranges,
                                  String text)
     : units_(std::move(units)), ranges_(std::move(ranges)), text_(text) {
 #if ENABLE_SECURITY_ASSERT
   for (const auto& unit : units_) {
     SECURITY_DCHECK(unit.TextContentStart() <= text.length())
         << unit.TextContentStart() << "<=" << text.length();
     SECURITY_DCHECK(unit.TextContentEnd() <= text.length())
         << unit.TextContentEnd() << "<=" << text.length();
     unit.AssertValid();
   }
   for (const auto& pair : ranges) {
     SECURITY_DCHECK(pair.value.first < units_.size())
         << pair.value.first << "<" << units_.size();
     SECURITY_DCHECK(pair.value.second < units_.size())
         << pair.value.second << "<" << units_.size();
   }
 #endif
 }

 NGOffsetMapping::~NGOffsetMapping() = default;

 const NGOffsetMappingUnit* NGOffsetMapping::GetMappingUnitForPosition(
     const Position& position) const {
   DCHECK(NGOffsetMapping::AcceptsPosition(position));
   const auto node_and_offset = ToNodeOffsetPair(position);
   const Node& node = node_and_offset.first;
   const unsigned offset = node_and_offset.second;
   unsigned range_start;
   unsigned range_end;
   std::tie(range_start, range_end) = ranges_.at(&node);
   if (range_start == range_end || units_[range_start].DOMStart() > offset)
     return nullptr;
   // Find the last unit where unit.dom_start <= offset
   const NGOffsetMappingUnit* unit = std::prev(std::upper_bound(
       units_.begin() + range_start, units_.begin() + range_end, offset,
       [](unsigned offset, const NGOffsetMappingUnit& unit) {
         return offset < unit.DOMStart();
       }));
   if (unit->DOMEnd() < offset)
     return nullptr;
   return unit;
 }

 NGOffsetMapping::UnitVector NGOffsetMapping::GetMappingUnitsForDOMRange(
     const EphemeralRange& range) const {
   DCHECK(NGOffsetMapping::AcceptsPosition(range.StartPosition()));
   DCHECK(NGOffsetMapping::AcceptsPosition(range.EndPosition()));
   DCHECK_EQ(range.StartPosition().AnchorNode(),
             range.EndPosition().AnchorNode());
   const Node& node = *range.StartPosition().AnchorNode();
   const unsigned start_offset = ToNodeOffsetPair(range.StartPosition()).second;
   const unsigned end_offset = ToNodeOffsetPair(range.EndPosition()).second;
   unsigned range_start;
   unsigned range_end;
   std::tie(range_start, range_end) = ranges_.at(&node);

   if (range_start == range_end || units_[range_start].DOMStart() > end_offset ||
       units_[range_end - 1].DOMEnd() < start_offset)
     return UnitVector();

   // Find the first unit where unit.dom_end >= start_offset
   const NGOffsetMappingUnit* result_begin = std::lower_bound(
       units_.begin() + range_start, units_.begin() + range_end, start_offset,
       [](const NGOffsetMappingUnit& unit, unsigned offset) {
         return unit.DOMEnd() < offset;
       });

   // Find the next of the last unit where unit.dom_start <= end_offset
   const NGOffsetMappingUnit* result_end =
       std::upper_bound(result_begin, units_.begin() + range_end, end_offset,
                        [](unsigned offset, const NGOffsetMappingUnit& unit) {
                          return offset < unit.DOMStart();
                        });

   UnitVector result;
   result.ReserveCapacity(result_end - result_begin);
   for (const auto& unit : base::make_span(result_begin, result_end)) {
     // If the unit isn't fully within the range, create a new unit that's
     // within the range.
     const unsigned clamped_start = std::max(unit.DOMStart(), start_offset);
     const unsigned clamped_end = std::min(unit.DOMEnd(), end_offset);
     DCHECK_LE(clamped_start, clamped_end);
     const unsigned clamped_text_content_start =
         unit.ConvertDOMOffsetToTextContent(clamped_start);
     const unsigned clamped_text_content_end =
         unit.ConvertDOMOffsetToTextContent(clamped_end);
     result.emplace_back(unit.GetType(), unit.GetLayoutObject(), clamped_start,
                         clamped_end, clamped_text_content_start,
                         clamped_text_content_end);
   }
   return result;
 }

 base::span<const NGOffsetMappingUnit> NGOffsetMapping::GetMappingUnitsForNode(
     const Node& node) const {
   const auto it = ranges_.find(&node);
   if (it == ranges_.end()) {
     NOTREACHED() << node;
     return {};
   }
   return base::make_span(units_.begin() + it->value.first,
                          units_.begin() + it->value.second);
 }

 base::span<const NGOffsetMappingUnit>
 NGOffsetMapping::GetMappingUnitsForLayoutObject(
     const LayoutObject& layout_object) const {
   const auto* begin =
       std::find_if(units_.begin(), units_.end(),
                    [&layout_object](const NGOffsetMappingUnit& unit) {
                      return unit.GetLayoutObject() == layout_object;
                    });
   CHECK_NE(begin, units_.end());
   const auto* end =
       std::find_if(std::next(begin), units_.end(),
                    [&layout_object](const NGOffsetMappingUnit& unit) {
                      return unit.GetLayoutObject() != layout_object;
                    });
   DCHECK_LT(begin, end);
   return base::make_span(begin, end);
 }

 base::span<const NGOffsetMappingUnit>
 NGOffsetMapping::GetMappingUnitsForTextContentOffsetRange(unsigned start,
                                                           unsigned end) const {
   DCHECK_LE(start, end);
   if (units_.front().TextContentStart() >= end ||
       units_.back().TextContentEnd() <= start)
     return {};

   // Find the first unit where unit.text_content_end > start
   const NGOffsetMappingUnit* result_begin =
       std::lower_bound(units_.begin(), units_.end(), start,
                        [](const NGOffsetMappingUnit& unit, unsigned offset) {
                          return unit.TextContentEnd() <= offset;
                        });
   if (result_begin == units_.end() || result_begin->TextContentStart() >= end)
     return {};

   // Find the next of the last unit where unit.text_content_start < end
   const NGOffsetMappingUnit* result_end =
       std::upper_bound(units_.begin(), units_.end(), end,
                        [](unsigned offset, const NGOffsetMappingUnit& unit) {
                          return offset <= unit.TextContentStart();
                        });
   return base::make_span(result_begin, result_end);
 }

 base::Optional<unsigned> NGOffsetMapping::GetTextContentOffset(
     const Position& position) const {
   DCHECK(NGOffsetMapping::AcceptsPosition(position)) << position;
   const NGOffsetMappingUnit* unit = GetMappingUnitForPosition(position);
   if (!unit)
     return base::nullopt;
   return unit->ConvertDOMOffsetToTextContent(ToNodeOffsetPair(position).second);
 }

 Position NGOffsetMapping::StartOfNextNonCollapsedContent(
     const Position& position) const {
   DCHECK(NGOffsetMapping::AcceptsPosition(position)) << position;
   const NGOffsetMappingUnit* unit = GetMappingUnitForPosition(position);
   if (!unit)
     return Position();

   const auto node_and_offset = ToNodeOffsetPair(position);
   const Node& node = node_and_offset.first;
   const unsigned offset = node_and_offset.second;
   while (unit != units_.end() && unit->AssociatedNode() == node) {
     if (unit->DOMEnd() > offset &&
         unit->GetType() != NGOffsetMappingUnitType::kCollapsed) {
       const unsigned result = std::max(offset, unit->DOMStart());
       return CreatePositionForOffsetMapping(node, result);
     }
     ++unit;
   }
   return Position();
 }

 Position NGOffsetMapping::EndOfLastNonCollapsedContent(
     const Position& position) const {
   DCHECK(NGOffsetMapping::AcceptsPosition(position)) << position;
   const NGOffsetMappingUnit* unit = GetMappingUnitForPosition(position);
   if (!unit)
     return Position();

   const auto node_and_offset = ToNodeOffsetPair(position);
   const Node& node = node_and_offset.first;
   const unsigned offset = node_and_offset.second;
   while (unit->AssociatedNode() == node) {
     if (unit->DOMStart() < offset &&
         unit->GetType() != NGOffsetMappingUnitType::kCollapsed) {
       const unsigned result = std::min(offset, unit->DOMEnd());
       return CreatePositionForOffsetMapping(node, result);
     }
     if (unit == units_.begin())
       break;
     --unit;
   }
   return Position();
 }

 bool NGOffsetMapping::IsBeforeNonCollapsedContent(
     const Position& position) const {
   DCHECK(NGOffsetMapping::AcceptsPosition(position));
   const NGOffsetMappingUnit* unit = GetMappingUnitForPosition(position);
   const unsigned offset = ToNodeOffsetPair(position).second;
   return unit && offset < unit->DOMEnd() &&
          unit->GetType() != NGOffsetMappingUnitType::kCollapsed;
 }

 bool NGOffsetMapping::IsAfterNonCollapsedContent(
     const Position& position) const {
   DCHECK(NGOffsetMapping::AcceptsPosition(position));
   const auto node_and_offset = ToNodeOffsetPair(position);
   const Node& node = node_and_offset.first;
   const unsigned offset = node_and_offset.second;
   if (!offset)
     return false;
   // In case we have one unit ending at |offset| and another starting at
   // |offset|, we need to find the former. Hence, search with |offset - 1|.
   const NGOffsetMappingUnit* unit = GetMappingUnitForPosition(
       CreatePositionForOffsetMapping(node, offset - 1));
   return unit && offset > unit->DOMStart() &&
          unit->GetType() != NGOffsetMappingUnitType::kCollapsed;
 }

 base::Optional<UChar> NGOffsetMapping::GetCharacterBefore(
     const Position& position) const {
   DCHECK(NGOffsetMapping::AcceptsPosition(position));
   base::Optional<unsigned> text_content_offset = GetTextContentOffset(position);
   if (!text_content_offset || !*text_content_offset)
     return base::nullopt;
   return text_[*text_content_offset - 1];
 }

 Position NGOffsetMapping::GetFirstPosition(unsigned offset) const {
   // Find the first unit where |unit.TextContentEnd() >= offset|
   if (units_.IsEmpty() || units_.back().TextContentEnd() < offset)
     return {};
   const NGOffsetMappingUnit* result =
       std::lower_bound(units_.begin(), units_.end(), offset,
                        [](const NGOffsetMappingUnit& unit, unsigned offset) {
                          return unit.TextContentEnd() < offset;
                        });
   CHECK_NE(result, units_.end());
   // Skip CSS generated content, e.g. "content" property in ::before/::after.
   while (!result->AssociatedNode()) {
     result = std::next(result);
     if (result == units_.end() || result->TextContentStart() > offset)
       return {};
   }
   const Node& node = result->GetOwner();
   const unsigned dom_offset =
       result->ConvertTextContentToFirstDOMOffset(offset);
   return CreatePositionForOffsetMapping(node, dom_offset);
 }

 const NGOffsetMappingUnit* NGOffsetMapping::GetFirstMappingUnit(
     unsigned offset) const {
   // Find the first unit where |unit.TextContentEnd() <= offset|
   if (units_.IsEmpty() || units_.front().TextContentStart() > offset)
     return nullptr;
   const NGOffsetMappingUnit* result =
       std::lower_bound(units_.begin(), units_.end(), offset,
                        [](const NGOffsetMappingUnit& unit, unsigned offset) {
                          return unit.TextContentEnd() < offset;
                        });
   if (result == units_.end())
     return nullptr;
   const NGOffsetMappingUnit* next_unit = std::next(result);
   if (next_unit != units_.end() && next_unit->TextContentStart() == offset) {
     // For offset=2, returns [1] instead of [0].
     // For offset=3, returns [3] instead of [2],
     // in below example:
     //  text_content = "ab\ncd"
     //  offset mapping unit:
     //   [0] I DOM:0-2 TC:0-2 "ab"
     //   [1] C DOM:2-3 TC:2-2
     //   [2] I DOM:3-4 TC:2-3 "\n"
     //   [3] C DOM:4-5 TC:3-3
     //   [4] I DOM:5-7 TC:3-5 "cd"
     return next_unit;
   }
   return result;
 }

 const NGOffsetMappingUnit* NGOffsetMapping::GetLastMappingUnit(
     unsigned offset) const {
   // Find the last unit where |unit.TextContentStart() <= offset|
   if (units_.IsEmpty() || units_.front().TextContentStart() > offset)
     return nullptr;
   const NGOffsetMappingUnit* result =
       std::upper_bound(units_.begin(), units_.end(), offset,
                        [](unsigned offset, const NGOffsetMappingUnit& unit) {
                          return offset < unit.TextContentStart();
                        });
   CHECK_NE(result, units_.begin());
   result = std::prev(result);
   if (result->TextContentEnd() < offset)
     return nullptr;
   return result;
 }

 Position NGOffsetMapping::GetLastPosition(unsigned offset) const {
   const NGOffsetMappingUnit* result = GetLastMappingUnit(offset);
   if (!result)
     return {};
   // Skip CSS generated content, e.g. "content" property in ::before/::after.
   while (!result->AssociatedNode()) {
     if (result == units_.begin())
       return {};
     result = std::prev(result);
     if (result->TextContentEnd() < offset)
       return {};
   }
   const Node& node = result->GetOwner();
   const unsigned dom_offset = result->ConvertTextContentToLastDOMOffset(offset);
   return CreatePositionForOffsetMapping(node, dom_offset);
 }

 bool NGOffsetMapping::HasBidiControlCharactersOnly(unsigned start,
                                                    unsigned end) const {
   DCHECK_LE(start, end);
   DCHECK_LE(end, text_.length());
   for (unsigned i = start; i < end; ++i) {
     if (!Character::IsBidiControl(text_[i]))
       return false;
   }
   return true;
 }

 }  // namespace blink
	// Copyright 2017 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/layout/ng/inline/ng_offset_mapping.h"

	#include <algorithm>
	#include "third_party/blink/renderer/core/dom/node.h"
	#include "third_party/blink/renderer/core/dom/node_computed_style.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/position.h"
	#include "third_party/blink/renderer/core/layout/layout_text_fragment.h"
	#include "third_party/blink/renderer/core/layout/ng/inline/ng_inline_node.h"
	#include "third_party/blink/renderer/core/layout/ng/ng_block_node.h"
	#include "third_party/blink/renderer/platform/text/character.h"

	namespace blink {

	namespace {

	// Note: LayoutFlowThread, used for multicol, can't provide offset mapping.
	bool CanUseNGOffsetMapping(const LayoutObject& object) {
	return object.IsLayoutBlockFlow() && !object.IsLayoutFlowThread();
	}

	Position CreatePositionForOffsetMapping(const Node& node, unsigned dom_offset) {
	if (auto* text_node = DynamicTo<Text>(node)) {
	// 'text-transform' may make the rendered text length longer than the
	// original text node, in which case we clamp the offset to avoid crashing.
	// TODO(crbug.com/750990): Support 'text-transform' to remove this hack.
	#if DCHECK_IS_ON()
	// Ensures that the clamping hack kicks in only with text-transform.
	if (node.ComputedStyleRef().TextTransform() == ETextTransform::kNone)
	DCHECK_LE(dom_offset, text_node->length());
	#endif
	const unsigned clamped_offset = std::min(dom_offset, text_node->length());
	return Position(&node, clamped_offset);
	}
	// For non-text-anchored position, the offset must be either 0 or 1.
	DCHECK_LE(dom_offset, 1u);
	return dom_offset ? Position::AfterNode(node) : Position::BeforeNode(node);
	}

	std::pair<const Node&, unsigned> ToNodeOffsetPair(const Position& position) {
	DCHECK(NGOffsetMapping::AcceptsPosition(position)) << position;
	if (auto* text_node = DynamicTo<Text>(position.AnchorNode())) {
	if (position.IsOffsetInAnchor())
	return {*position.AnchorNode(), position.OffsetInContainerNode()};
	if (position.IsBeforeAnchor())
	return {*position.AnchorNode(), 0};
	DCHECK(position.IsAfterAnchor());
	return {*position.AnchorNode(), text_node->length()};
	}
	if (position.IsBeforeAnchor())
	return {*position.AnchorNode(), 0};
	return {*position.AnchorNode(), 1};
	}

	// TODO(xiaochengh): Introduce predicates for comparing Position and
	// NGOffsetMappingUnit, to reduce position-offset conversion and ad-hoc
	// predicates below.

	} // namespace

	LayoutBlockFlow* NGInlineFormattingContextOf(const Position& position) {
	if (!RuntimeEnabledFeatures::LayoutNGEnabled())
	return nullptr;
	LayoutBlockFlow* block_flow =
	NGOffsetMapping::GetInlineFormattingContextOf(position);
	if (!block_flow \|\| !block_flow->IsLayoutNGMixin())
	return nullptr;
	return block_flow;
	}

	// static
	LayoutBlockFlow* NGOffsetMapping::GetInlineFormattingContextOf(
	const Position& position) {
	if (!AcceptsPosition(position))
	return nullptr;
	const auto node_offset_pair = ToNodeOffsetPair(position);
	const LayoutObject* layout_object =
	AssociatedLayoutObjectOf(node_offset_pair.first, node_offset_pair.second);
	if (!layout_object)
	return nullptr;
	return GetInlineFormattingContextOf(*layout_object);
	}

	NGOffsetMappingUnit::NGOffsetMappingUnit(NGOffsetMappingUnitType type,
	const LayoutObject& layout_object,
	unsigned dom_start,
	unsigned dom_end,
	unsigned text_content_start,
	unsigned text_content_end)
	: type_(type),
	layout_object_(&layout_object),
	dom_start_(dom_start),
	dom_end_(dom_end),
	text_content_start_(text_content_start),
	text_content_end_(text_content_end) {
	AssertValid();
	}

	void NGOffsetMappingUnit::AssertValid() const {
	#if ENABLE_SECURITY_ASSERT
	SECURITY_DCHECK(dom_start_ <= dom_end_) << dom_start_ << " vs. " << dom_end_;
	SECURITY_DCHECK(text_content_start_ <= text_content_end_)
	<< text_content_start_ << " vs. " << text_content_end_;
	if (layout_object_->IsText() &&
	!To<LayoutText>(*layout_object_).IsWordBreak()) {
	const auto& layout_text = To<LayoutText>(*layout_object_);
	const unsigned text_start =
	AssociatedNode() ? layout_text.TextStartOffset() : 0;
	const unsigned text_end = text_start + layout_text.TextLength();
	SECURITY_DCHECK(dom_end_ >= text_start)
	<< dom_end_ << " vs. " << text_start;
	SECURITY_DCHECK(dom_end_ <= text_end) << dom_end_ << " vs. " << text_end;
	} else {
	SECURITY_DCHECK(dom_start_ == 0) << dom_start_;
	SECURITY_DCHECK(dom_end_ == 1) << dom_end_;
	}
	#endif
	}

	const Node* NGOffsetMappingUnit::AssociatedNode() const {
	if (const auto* text_fragment = DynamicTo<LayoutTextFragment>(layout_object_))
	return text_fragment->AssociatedTextNode();
	return layout_object_->GetNode();
	}

	const Node& NGOffsetMappingUnit::GetOwner() const {
	const Node* const node = AssociatedNode();
	DCHECK(node) << layout_object_;
	return *node;
	}

	bool NGOffsetMappingUnit::Concatenate(const NGOffsetMappingUnit& other) {
	if (layout_object_ != other.layout_object_)
	return false;
	if (type_ != other.type_)
	return false;
	if (dom_end_ != other.dom_start_)
	return false;
	if (text_content_end_ != other.text_content_start_)
	return false;
	// Don't merge first letter and remaining text
	if (const auto* text_fragment =
	DynamicTo<LayoutTextFragment>(layout_object_)) {
	// TODO(layout-dev): Fix offset calculation for text-transform
	if (text_fragment->IsRemainingTextLayoutObject() &&
	other.dom_start_ == text_fragment->TextStartOffset())
	return false;
	}
	dom_end_ = other.dom_end_;
	text_content_end_ = other.text_content_end_;
	return true;
	}

	unsigned NGOffsetMappingUnit::ConvertDOMOffsetToTextContent(
	unsigned offset) const {
	DCHECK_GE(offset, dom_start_);
	DCHECK_LE(offset, dom_end_);
	// DOM start is always mapped to text content start.
	if (offset == dom_start_)
	return text_content_start_;
	// DOM end is always mapped to text content end.
	if (offset == dom_end_)
	return text_content_end_;
	// Handle collapsed mapping.
	if (text_content_start_ == text_content_end_)
	return text_content_start_;
	// Handle has identity mapping.
	return offset - dom_start_ + text_content_start_;
	}

	unsigned NGOffsetMappingUnit::ConvertTextContentToFirstDOMOffset(
	unsigned offset) const {
	DCHECK_GE(offset, text_content_start_);
	DCHECK_LE(offset, text_content_end_);
	// Always return DOM start for collapsed units.
	if (text_content_start_ == text_content_end_)
	return dom_start_;
	// Handle identity mapping.
	if (type_ == NGOffsetMappingUnitType::kIdentity)
	return dom_start_ + offset - text_content_start_;
	// Handle expanded mapping.
	return offset < text_content_end_ ? dom_start_ : dom_end_;
	}

	unsigned NGOffsetMappingUnit::ConvertTextContentToLastDOMOffset(
	unsigned offset) const {
	DCHECK_GE(offset, text_content_start_);
	DCHECK_LE(offset, text_content_end_);
	// Always return DOM end for collapsed units.
	if (text_content_start_ == text_content_end_)
	return dom_end_;
	// In a non-collapsed unit, mapping between DOM and text content offsets is
	// one-to-one. Reuse existing code.
	return ConvertTextContentToFirstDOMOffset(offset);
	}

	// static
	bool NGOffsetMapping::AcceptsPosition(const Position& position) {
	if (position.IsNull())
	return false;
	if (position.AnchorNode()->IsTextNode()) {
	// Position constructor should have rejected other anchor types.
	DCHECK(position.IsOffsetInAnchor() \|\| position.IsBeforeAnchor() \|\|
	position.IsAfterAnchor());
	return true;
	}
	if (!position.IsBeforeAnchor() && !position.IsAfterAnchor())
	return false;
	const LayoutObject* layout_object = position.AnchorNode()->GetLayoutObject();
	if (!layout_object \|\| !layout_object->IsInline())
	return false;
	return layout_object->IsText() \|\| layout_object->IsAtomicInlineLevel();
	}

	// static
	const NGOffsetMapping* NGOffsetMapping::GetFor(const Position& position) {
	if (!RuntimeEnabledFeatures::LayoutNGEnabled())
	return nullptr;
	if (!NGOffsetMapping::AcceptsPosition(position))
	return nullptr;
	LayoutBlockFlow* context = NGInlineFormattingContextOf(position);
	if (!context)
	return nullptr;
	return NGInlineNode::GetOffsetMapping(context);
	}

	// static
	const NGOffsetMapping* NGOffsetMapping::GetFor(
	const LayoutObject* layout_object) {
	if (!RuntimeEnabledFeatures::LayoutNGEnabled())
	return nullptr;
	if (!layout_object)
	return nullptr;
	LayoutBlockFlow* context = layout_object->ContainingNGBlockFlow();
	if (!context)
	return nullptr;
	return NGInlineNode::GetOffsetMapping(context);
	}

	// static
	LayoutBlockFlow* NGOffsetMapping::GetInlineFormattingContextOf(
	const LayoutObject& object) {
	for (LayoutObject* runner = object.Parent(); runner;
	runner = runner->Parent()) {
	if (!CanUseNGOffsetMapping(*runner))
	continue;
	return To<LayoutBlockFlow>(runner);
	}
	return nullptr;
	}

	NGOffsetMapping::NGOffsetMapping(UnitVector&& units,
	RangeMap&& ranges,
	String text)
	: units_(std::move(units)), ranges_(std::move(ranges)), text_(text) {
	#if ENABLE_SECURITY_ASSERT
	for (const auto& unit : units_) {
	SECURITY_DCHECK(unit.TextContentStart() <= text.length())
	<< unit.TextContentStart() << "<=" << text.length();
	SECURITY_DCHECK(unit.TextContentEnd() <= text.length())
	<< unit.TextContentEnd() << "<=" << text.length();
	unit.AssertValid();
	}
	for (const auto& pair : ranges) {
	SECURITY_DCHECK(pair.value.first < units_.size())
	<< pair.value.first << "<" << units_.size();
	SECURITY_DCHECK(pair.value.second < units_.size())
	<< pair.value.second << "<" << units_.size();
	}
	#endif
	}

	NGOffsetMapping::~NGOffsetMapping() = default;

	const NGOffsetMappingUnit* NGOffsetMapping::GetMappingUnitForPosition(
	const Position& position) const {
	DCHECK(NGOffsetMapping::AcceptsPosition(position));
	const auto node_and_offset = ToNodeOffsetPair(position);
	const Node& node = node_and_offset.first;
	const unsigned offset = node_and_offset.second;
	unsigned range_start;
	unsigned range_end;
	std::tie(range_start, range_end) = ranges_.at(&node);
	if (range_start == range_end \|\| units_[range_start].DOMStart() > offset)
	return nullptr;
	// Find the last unit where unit.dom_start <= offset
	const NGOffsetMappingUnit* unit = std::prev(std::upper_bound(
	units_.begin() + range_start, units_.begin() + range_end, offset,
	[](unsigned offset, const NGOffsetMappingUnit& unit) {
	return offset < unit.DOMStart();
	}));
	if (unit->DOMEnd() < offset)
	return nullptr;
	return unit;
	}

	NGOffsetMapping::UnitVector NGOffsetMapping::GetMappingUnitsForDOMRange(
	const EphemeralRange& range) const {
	DCHECK(NGOffsetMapping::AcceptsPosition(range.StartPosition()));
	DCHECK(NGOffsetMapping::AcceptsPosition(range.EndPosition()));
	DCHECK_EQ(range.StartPosition().AnchorNode(),
	range.EndPosition().AnchorNode());
	const Node& node = *range.StartPosition().AnchorNode();
	const unsigned start_offset = ToNodeOffsetPair(range.StartPosition()).second;
	const unsigned end_offset = ToNodeOffsetPair(range.EndPosition()).second;
	unsigned range_start;
	unsigned range_end;
	std::tie(range_start, range_end) = ranges_.at(&node);

	if (range_start == range_end \|\| units_[range_start].DOMStart() > end_offset \|\|
	units_[range_end - 1].DOMEnd() < start_offset)
	return UnitVector();

	// Find the first unit where unit.dom_end >= start_offset
	const NGOffsetMappingUnit* result_begin = std::lower_bound(
	units_.begin() + range_start, units_.begin() + range_end, start_offset,
	[](const NGOffsetMappingUnit& unit, unsigned offset) {
	return unit.DOMEnd() < offset;
	});

	// Find the next of the last unit where unit.dom_start <= end_offset
	const NGOffsetMappingUnit* result_end =
	std::upper_bound(result_begin, units_.begin() + range_end, end_offset,
	[](unsigned offset, const NGOffsetMappingUnit& unit) {
	return offset < unit.DOMStart();
	});

	UnitVector result;
	result.ReserveCapacity(result_end - result_begin);
	for (const auto& unit : base::make_span(result_begin, result_end)) {
	// If the unit isn't fully within the range, create a new unit that's
	// within the range.
	const unsigned clamped_start = std::max(unit.DOMStart(), start_offset);
	const unsigned clamped_end = std::min(unit.DOMEnd(), end_offset);
	DCHECK_LE(clamped_start, clamped_end);
	const unsigned clamped_text_content_start =
	unit.ConvertDOMOffsetToTextContent(clamped_start);
	const unsigned clamped_text_content_end =
	unit.ConvertDOMOffsetToTextContent(clamped_end);
	result.emplace_back(unit.GetType(), unit.GetLayoutObject(), clamped_start,
	clamped_end, clamped_text_content_start,
	clamped_text_content_end);
	}
	return result;
	}

	base::span<const NGOffsetMappingUnit> NGOffsetMapping::GetMappingUnitsForNode(
	const Node& node) const {
	const auto it = ranges_.find(&node);
	if (it == ranges_.end()) {
	NOTREACHED() << node;
	return {};
	}
	return base::make_span(units_.begin() + it->value.first,
	units_.begin() + it->value.second);
	}

	base::span<const NGOffsetMappingUnit>
	NGOffsetMapping::GetMappingUnitsForLayoutObject(
	const LayoutObject& layout_object) const {
	const auto* begin =
	std::find_if(units_.begin(), units_.end(),
	[&layout_object](const NGOffsetMappingUnit& unit) {
	return unit.GetLayoutObject() == layout_object;
	});
	CHECK_NE(begin, units_.end());
	const auto* end =
	std::find_if(std::next(begin), units_.end(),
	[&layout_object](const NGOffsetMappingUnit& unit) {
	return unit.GetLayoutObject() != layout_object;
	});
	DCHECK_LT(begin, end);
	return base::make_span(begin, end);
	}

	base::span<const NGOffsetMappingUnit>
	NGOffsetMapping::GetMappingUnitsForTextContentOffsetRange(unsigned start,
	unsigned end) const {
	DCHECK_LE(start, end);
	if (units_.front().TextContentStart() >= end \|\|
	units_.back().TextContentEnd() <= start)
	return {};

	// Find the first unit where unit.text_content_end > start
	const NGOffsetMappingUnit* result_begin =
	std::lower_bound(units_.begin(), units_.end(), start,
	[](const NGOffsetMappingUnit& unit, unsigned offset) {
	return unit.TextContentEnd() <= offset;
	});
	if (result_begin == units_.end() \|\| result_begin->TextContentStart() >= end)
	return {};

	// Find the next of the last unit where unit.text_content_start < end
	const NGOffsetMappingUnit* result_end =
	std::upper_bound(units_.begin(), units_.end(), end,
	[](unsigned offset, const NGOffsetMappingUnit& unit) {
	return offset <= unit.TextContentStart();
	});
	return base::make_span(result_begin, result_end);
	}

	base::Optional<unsigned> NGOffsetMapping::GetTextContentOffset(
	const Position& position) const {
	DCHECK(NGOffsetMapping::AcceptsPosition(position)) << position;
	const NGOffsetMappingUnit* unit = GetMappingUnitForPosition(position);
	if (!unit)
	return base::nullopt;
	return unit->ConvertDOMOffsetToTextContent(ToNodeOffsetPair(position).second);
	}

	Position NGOffsetMapping::StartOfNextNonCollapsedContent(
	const Position& position) const {
	DCHECK(NGOffsetMapping::AcceptsPosition(position)) << position;
	const NGOffsetMappingUnit* unit = GetMappingUnitForPosition(position);
	if (!unit)
	return Position();

	const auto node_and_offset = ToNodeOffsetPair(position);
	const Node& node = node_and_offset.first;
	const unsigned offset = node_and_offset.second;
	while (unit != units_.end() && unit->AssociatedNode() == node) {
	if (unit->DOMEnd() > offset &&
	unit->GetType() != NGOffsetMappingUnitType::kCollapsed) {
	const unsigned result = std::max(offset, unit->DOMStart());
	return CreatePositionForOffsetMapping(node, result);
	}
	++unit;
	}
	return Position();
	}

	Position NGOffsetMapping::EndOfLastNonCollapsedContent(
	const Position& position) const {
	DCHECK(NGOffsetMapping::AcceptsPosition(position)) << position;
	const NGOffsetMappingUnit* unit = GetMappingUnitForPosition(position);
	if (!unit)
	return Position();

	const auto node_and_offset = ToNodeOffsetPair(position);
	const Node& node = node_and_offset.first;
	const unsigned offset = node_and_offset.second;
	while (unit->AssociatedNode() == node) {
	if (unit->DOMStart() < offset &&
	unit->GetType() != NGOffsetMappingUnitType::kCollapsed) {
	const unsigned result = std::min(offset, unit->DOMEnd());
	return CreatePositionForOffsetMapping(node, result);
	}
	if (unit == units_.begin())
	break;
	--unit;
	}
	return Position();
	}

	bool NGOffsetMapping::IsBeforeNonCollapsedContent(
	const Position& position) const {
	DCHECK(NGOffsetMapping::AcceptsPosition(position));
	const NGOffsetMappingUnit* unit = GetMappingUnitForPosition(position);
	const unsigned offset = ToNodeOffsetPair(position).second;
	return unit && offset < unit->DOMEnd() &&
	unit->GetType() != NGOffsetMappingUnitType::kCollapsed;
	}

	bool NGOffsetMapping::IsAfterNonCollapsedContent(
	const Position& position) const {
	DCHECK(NGOffsetMapping::AcceptsPosition(position));
	const auto node_and_offset = ToNodeOffsetPair(position);
	const Node& node = node_and_offset.first;
	const unsigned offset = node_and_offset.second;
	if (!offset)
	return false;
	// In case we have one unit ending at \|offset\| and another starting at
	// \|offset\|, we need to find the former. Hence, search with \|offset - 1\|.
	const NGOffsetMappingUnit* unit = GetMappingUnitForPosition(
	CreatePositionForOffsetMapping(node, offset - 1));
	return unit && offset > unit->DOMStart() &&
	unit->GetType() != NGOffsetMappingUnitType::kCollapsed;
	}

	base::Optional<UChar> NGOffsetMapping::GetCharacterBefore(
	const Position& position) const {
	DCHECK(NGOffsetMapping::AcceptsPosition(position));
	base::Optional<unsigned> text_content_offset = GetTextContentOffset(position);
	if (!text_content_offset \|\| !*text_content_offset)
	return base::nullopt;
	return text_[*text_content_offset - 1];
	}

	Position NGOffsetMapping::GetFirstPosition(unsigned offset) const {
	// Find the first unit where \|unit.TextContentEnd() >= offset\|
	if (units_.IsEmpty() \|\| units_.back().TextContentEnd() < offset)
	return {};
	const NGOffsetMappingUnit* result =
	std::lower_bound(units_.begin(), units_.end(), offset,
	[](const NGOffsetMappingUnit& unit, unsigned offset) {
	return unit.TextContentEnd() < offset;
	});
	CHECK_NE(result, units_.end());
	// Skip CSS generated content, e.g. "content" property in ::before/::after.
	while (!result->AssociatedNode()) {
	result = std::next(result);
	if (result == units_.end() \|\| result->TextContentStart() > offset)
	return {};
	}
	const Node& node = result->GetOwner();
	const unsigned dom_offset =
	result->ConvertTextContentToFirstDOMOffset(offset);
	return CreatePositionForOffsetMapping(node, dom_offset);
	}

	const NGOffsetMappingUnit* NGOffsetMapping::GetFirstMappingUnit(
	unsigned offset) const {
	// Find the first unit where \|unit.TextContentEnd() <= offset\|
	if (units_.IsEmpty() \|\| units_.front().TextContentStart() > offset)
	return nullptr;
	const NGOffsetMappingUnit* result =
	std::lower_bound(units_.begin(), units_.end(), offset,
	[](const NGOffsetMappingUnit& unit, unsigned offset) {
	return unit.TextContentEnd() < offset;
	});
	if (result == units_.end())
	return nullptr;
	const NGOffsetMappingUnit* next_unit = std::next(result);
	if (next_unit != units_.end() && next_unit->TextContentStart() == offset) {
	// For offset=2, returns [1] instead of [0].
	// For offset=3, returns [3] instead of [2],
	// in below example:
	// text_content = "ab\ncd"
	// offset mapping unit:
	// [0] I DOM:0-2 TC:0-2 "ab"
	// [1] C DOM:2-3 TC:2-2
	// [2] I DOM:3-4 TC:2-3 "\n"
	// [3] C DOM:4-5 TC:3-3
	// [4] I DOM:5-7 TC:3-5 "cd"
	return next_unit;
	}
	return result;
	}

	const NGOffsetMappingUnit* NGOffsetMapping::GetLastMappingUnit(
	unsigned offset) const {
	// Find the last unit where \|unit.TextContentStart() <= offset\|
	if (units_.IsEmpty() \|\| units_.front().TextContentStart() > offset)
	return nullptr;
	const NGOffsetMappingUnit* result =
	std::upper_bound(units_.begin(), units_.end(), offset,
	[](unsigned offset, const NGOffsetMappingUnit& unit) {
	return offset < unit.TextContentStart();
	});
	CHECK_NE(result, units_.begin());
	result = std::prev(result);
	if (result->TextContentEnd() < offset)
	return nullptr;
	return result;
	}

	Position NGOffsetMapping::GetLastPosition(unsigned offset) const {
	const NGOffsetMappingUnit* result = GetLastMappingUnit(offset);
	if (!result)
	return {};
	// Skip CSS generated content, e.g. "content" property in ::before/::after.
	while (!result->AssociatedNode()) {
	if (result == units_.begin())
	return {};
	result = std::prev(result);
	if (result->TextContentEnd() < offset)
	return {};
	}
	const Node& node = result->GetOwner();
	const unsigned dom_offset = result->ConvertTextContentToLastDOMOffset(offset);
	return CreatePositionForOffsetMapping(node, dom_offset);
	}

	bool NGOffsetMapping::HasBidiControlCharactersOnly(unsigned start,
	unsigned end) const {
	DCHECK_LE(start, end);
	DCHECK_LE(end, text_.length());
	for (unsigned i = start; i < end; ++i) {
	if (!Character::IsBidiControl(text_[i]))
	return false;
	}
	return true;
	}

	} // namespace blink