/*
 * Copyright (C) 2007, 2009 Apple Inc. All rights reserved.
 * Copyright (C) 2012 Google Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1.  Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 * 2.  Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
 *     its contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "third_party/blink/renderer/core/editing/dom_selection.h"

#include "third_party/blink/renderer/bindings/core/v8/v8_get_composed_ranges_options.h"
#include "third_party/blink/renderer/core/dom/document.h"
#include "third_party/blink/renderer/core/dom/node.h"
#include "third_party/blink/renderer/core/dom/range.h"
#include "third_party/blink/renderer/core/dom/tree_scope.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/frame_selection.h"
#include "third_party/blink/renderer/core/editing/iterators/text_iterator.h"
#include "third_party/blink/renderer/core/editing/position.h"
#include "third_party/blink/renderer/core/editing/selection_modifier.h"
#include "third_party/blink/renderer/core/editing/selection_template.h"
#include "third_party/blink/renderer/core/editing/set_selection_options.h"
#include "third_party/blink/renderer/core/editing/visible_selection.h"
#include "third_party/blink/renderer/core/frame/local_dom_window.h"
#include "third_party/blink/renderer/core/frame/local_frame.h"
#include "third_party/blink/renderer/core/inspector/console_message.h"
#include "third_party/blink/renderer/platform/bindings/exception_state.h"
#include "third_party/blink/renderer/platform/heap/garbage_collected.h"
#include "third_party/blink/renderer/platform/instrumentation/use_counter.h"
#include "third_party/blink/renderer/platform/runtime_enabled_features.h"
#include "third_party/blink/renderer/platform/wtf/text/wtf_string.h"

namespace blink {

DomSelection::DomSelection(const TreeScope* tree_scope)
    : ExecutionContextClient(tree_scope->RootNode().GetExecutionContext()),
      tree_scope_(tree_scope) {}

void DomSelection::ClearTreeScope() {
  tree_scope_ = nullptr;
}

FrameSelection& DomSelection::Selection() const {
  DCHECK(DomWindow());
  return DomWindow()->GetFrame()->Selection();
}

// TODO(editing-dev): The behavior after loosing browsing context is not
// specified. https://github.com/w3c/selection-api/issues/82
bool DomSelection::IsAvailable() const {
  return DomWindow() && Selection().IsAvailable();
}

void DomSelection::UpdateFrameSelection(
    const SelectionInDomTree& selection,
    Range* new_cached_range,
    const SetSelectionOptions& passed_options) const {
  DCHECK(DomWindow());
  SetSelectionOptions::Builder builder(passed_options);
  builder.SetShouldCloseTyping(true).SetShouldClearTypingStyle(true);
  SetSelectionOptions options = builder.Build();
  // TODO(tkent): Specify FrameSelection::DoNotSetFocus. crbug.com/690272
  const bool did_set = Selection().SetSelectionDeprecated(selection, options);
  CacheRangeIfSelectionOfDocument(new_cached_range);
  if (!did_set)
    return;
  Element* focused_element = DomWindow()->document()->FocusedElement();
  Selection().DidSetSelectionDeprecated(selection, options);
  if (DomWindow() &&
      focused_element != DomWindow()->document()->FocusedElement()) {
    UseCounter::Count(DomWindow(), WebFeature::kSelectionFuncionsChangeFocus);
  }
}

VisibleSelection DomSelection::GetVisibleSelection() const {
  // TODO(editing-dev): The use of UpdateStyleAndLayout
  // needs to be audited.  See http://crbug.com/590369 for more details.
  DomWindow()->document()->UpdateStyleAndLayout(
      DocumentUpdateReason::kSelection);

  return Selection().ComputeVisibleSelectionInDomTree();
}

bool DomSelection::IsAnchorFirstInSelection() const {
  return Selection().GetSelectionInDomTree().IsAnchorFirst();
}

Node* DomSelection::anchorNode() const {
  TemporaryRange temp_range(this, PrimaryRangeOrNull());
  if (temp_range.GetRange()) {
    if (!DomWindow() || IsAnchorFirstInSelection()) {
      return temp_range.GetRange()->startContainer();
    }
    return temp_range.GetRange()->endContainer();
  }
  return nullptr;
}

wtf_size_t DomSelection::anchorOffset() const {
  TemporaryRange temp_range(this, PrimaryRangeOrNull());
  if (temp_range.GetRange()) {
    if (!DomWindow() || IsAnchorFirstInSelection()) {
      return temp_range.GetRange()->startOffset();
    }
    return temp_range.GetRange()->endOffset();
  }
  return 0;
}

Node* DomSelection::focusNode() const {
  TemporaryRange temp_range(this, PrimaryRangeOrNull());
  if (temp_range.GetRange()) {
    if (!DomWindow() || IsAnchorFirstInSelection()) {
      return temp_range.GetRange()->endContainer();
    }
    return temp_range.GetRange()->startContainer();
  }
  return nullptr;
}

wtf_size_t DomSelection::focusOffset() const {
  TemporaryRange temp_range(this, PrimaryRangeOrNull());
  if (temp_range.GetRange()) {
    if (!DomWindow() || IsAnchorFirstInSelection()) {
      return temp_range.GetRange()->endOffset();
    }
    return temp_range.GetRange()->startOffset();
  }
  return 0;
}

Node* DomSelection::baseNode() const {
  return anchorNode();
}

wtf_size_t DomSelection::baseOffset() const {
  return anchorOffset();
}

Node* DomSelection::extentNode() const {
  return focusNode();
}

wtf_size_t DomSelection::extentOffset() const {
  return focusOffset();
}

bool DomSelection::isCollapsed() const {
  if (!IsAvailable())
    return true;
  // TODO(editing-dev): The use of UpdateStyleAndLayout
  // needs to be audited.  See http://crbug.com/590369 for more details.
  DomWindow()->document()->UpdateStyleAndLayout(
      DocumentUpdateReason::kSelection);

  TemporaryRange temp_range(this, PrimaryRangeOrNull());
  if (temp_range.GetRange()) {
    return temp_range.GetRange()->collapsed();
  }
  return true;
}

String DomSelection::type() const {
  if (!IsAvailable())
    return String();
  // This is a WebKit DOM extension, incompatible with an IE extension
  // IE has this same attribute, but returns "none", "text" and "control"
  // http://msdn.microsoft.com/en-us/library/ms534692(VS.85).aspx
  if (rangeCount() == 0)
    return "None";
  // Do not use isCollapsed() here. We'd like to return "Range" for
  // range-selection in text control elements.
  if (Selection().GetSelectionInDomTree().IsCaret()) {
    return "Caret";
  }
  return "Range";
}

String DomSelection::direction() const {
  if (!IsAvailable()) {
    return "none";
  }
  // TODO(editing-dev): The use of UpdateStyleAndLayout
  // needs to be audited.  See http://crbug.com/590369 for more details.
  DomWindow()->document()->UpdateStyleAndLayout(
      DocumentUpdateReason::kSelection);

  if (!Selection().IsDirectional() ||
      (RuntimeEnabledFeatures::SelectionCollapsedDirectionNoneEnabled() &&
       // Use IsCaret() instead of isCollapsed() so that directionality is still
       // reported for selections that cross shadow boundaries.
       Selection().GetSelectionInDomTree().IsCaret()) ||
      Selection().ComputeVisibleSelectionInDomTree().IsNone()) {
    return "none";
  }
  if (IsAnchorFirstInSelection()) {
    return "forward";
  }
  return "backward";
}

wtf_size_t DomSelection::rangeCount() const {
  if (!IsAvailable())
    return 0;
  if (DocumentCachedRange())
    return 1;

  // TODO(editing-dev): The use of UpdateStyleAndLayout
  // needs to be audited.  See http://crbug.com/590369 for more details.
  DomWindow()->document()->UpdateStyleAndLayout(
      DocumentUpdateReason::kSelection);

  if (Selection().ComputeVisibleSelectionInDomTree().IsNone()) {
    return 0;
  }
  // Any selection can be adjusted to Range for Document.
  if (IsSelectionOfDocument())
    return 1;
  // In ShadowRoot, we need to try adjustment.
  if (CreateRangeFromSelectionEditor().IsNotNull())
    return 1;
  return 0;
}

// https://www.w3.org/TR/selection-api/#dom-selection-collapse
void DomSelection::collapse(Node* node,
                            wtf_size_t offset,
                            ExceptionState& exception_state) {
  if (!IsAvailable())
    return;

  // 1. If node is null, this method must behave identically as
  // removeAllRanges() and abort these steps.
  if (!node) {
    UseCounter::Count(DomWindow(), WebFeature::kSelectionCollapseNull);
    Selection().Clear();
    return;
  }

  // 2. The method must throw an IndexSizeError exception if offset is longer
  // than node's length ([DOM4]) and abort these steps.
  Range::CheckNodeWOffset(node, offset, exception_state);
  if (exception_state.HadException())
    return;

  // 3. If document associated with this is not a shadow-including inclusive
  // ancestor of node, abort these steps.
  if (!IsValidForPosition(node))
    return;

  // 4. Otherwise, let newRange be a new range.
  Range* new_range = Range::Create(*DomWindow()->document());

  // 5. Set ([DOM4]) the start and the end of newRange to (node, offset).
  new_range->setStart(node, offset, exception_state);
  if (exception_state.HadException()) {
    new_range->Dispose();
    return;
  }
  new_range->setEnd(node, offset, exception_state);
  if (exception_state.HadException()) {
    new_range->Dispose();
    return;
  }

  // 6. Set the context object's range to newRange.
  UpdateFrameSelection(
      SelectionInDomTree::Builder().Collapse(Position(node, offset)).Build(),
      new_range,
      SetSelectionOptions::Builder()
          .SetIsDirectional(Selection().IsDirectional())
          .Build());
}

// https://www.w3.org/TR/selection-api/#dom-selection-collapsetoend
void DomSelection::collapseToEnd(ExceptionState& exception_state) {
  if (!IsAvailable())
    return;

  // The method must throw InvalidStateError exception if the context object is
  // empty.
  if (rangeCount() == 0) {
    exception_state.ThrowDOMException(DOMExceptionCode::kInvalidStateError,
                                      "there is no selection.");
    return;
  }

  if (Range* current_range = DocumentCachedRange()) {
    // Otherwise, it must create a new range, set both its start and end to the
    // end of the context object's range,
    Range* new_range = current_range->cloneRange();
    new_range->collapse(false);

    // and then set the context object's range to the newly-created range.
    SelectionInDomTree::Builder builder;
    builder.Collapse(new_range->EndPosition());
    UpdateFrameSelection(builder.Build(), new_range, SetSelectionOptions());
  } else {
    // TODO(tkent): The Selection API doesn't define this behavior. We should
    // discuss this on https://github.com/w3c/selection-api/issues/83.
    SelectionInDomTree::Builder builder;
    builder.Collapse(Selection().GetSelectionInDomTree().ComputeEndPosition());
    UpdateFrameSelection(builder.Build(), nullptr, SetSelectionOptions());
  }
}

// https://www.w3.org/TR/selection-api/#dom-selection-collapsetostart
void DomSelection::collapseToStart(ExceptionState& exception_state) {
  if (!IsAvailable())
    return;

  // The method must throw InvalidStateError ([DOM4]) exception if the context
  // object is empty.
  if (rangeCount() == 0) {
    exception_state.ThrowDOMException(DOMExceptionCode::kInvalidStateError,
                                      "there is no selection.");
    return;
  }

  if (Range* current_range = DocumentCachedRange()) {
    // Otherwise, it must create a new range, set both its start and end to the
    // start of the context object's range,
    Range* new_range = current_range->cloneRange();
    new_range->collapse(true);

    // and then set the context object's range to the newly-created range.
    SelectionInDomTree::Builder builder;
    builder.Collapse(new_range->StartPosition());
    UpdateFrameSelection(builder.Build(), new_range, SetSelectionOptions());
  } else {
    // TODO(tkent): The Selection API doesn't define this behavior. We should
    // discuss this on https://github.com/w3c/selection-api/issues/83.
    SelectionInDomTree::Builder builder;
    builder.Collapse(
        Selection().GetSelectionInDomTree().ComputeStartPosition());
    UpdateFrameSelection(builder.Build(), nullptr, SetSelectionOptions());
  }
}

void DomSelection::empty() {
  if (IsAvailable())
    Selection().Clear();
}

// https://www.w3.org/TR/selection-api/#dom-selection-setbaseandextent
void DomSelection::setBaseAndExtent(Node* base_node,
                                    wtf_size_t base_offset,
                                    Node* extent_node,
                                    wtf_size_t extent_offset,
                                    ExceptionState& exception_state) {
  if (!IsAvailable())
    return;

  // TODO(editing-dev): Behavior on where base or extent is null is still
  // under discussion: https://github.com/w3c/selection-api/issues/72
  if (RuntimeEnabledFeatures::SelectionSetBaseAndExtentNonNullNodeEnabled()) {
    if (!base_node) {
      UseCounter::Count(DomWindow(),
                        WebFeature::kSelectionSetBaseAndExtentNull);
      exception_state.ThrowTypeError("anchorNode is null");
      return;
    }
    if (!extent_node) {
      UseCounter::Count(DomWindow(),
                        WebFeature::kSelectionSetBaseAndExtentNull);
      exception_state.ThrowTypeError("focusNode is null");
      return;
    }
  } else {
    if (!base_node) {
      UseCounter::Count(DomWindow(),
                        WebFeature::kSelectionSetBaseAndExtentNull);
      Selection().Clear();
      return;
    }
    if (!extent_node) {
      UseCounter::Count(DomWindow(),
                        WebFeature::kSelectionSetBaseAndExtentNull);
      extent_offset = 0;
    }
  }

  // 1. If anchorOffset is longer than anchorNode's length or if focusOffset is
  // longer than focusNode's length, throw an IndexSizeError exception and abort
  // these steps.
  Range::CheckNodeWOffset(base_node, base_offset, exception_state);
  if (exception_state.HadException())
    return;
  if (extent_node) {
    Range::CheckNodeWOffset(extent_node, extent_offset, exception_state);
    if (exception_state.HadException())
      return;
  }

  // 2. If document associated with this is not a shadow-including inclusive
  // ancestor of anchorNode or focusNode, abort these steps.
  if (!IsValidForPosition(base_node) || !IsValidForPosition(extent_node))
    return;

  ClearCachedRangeIfSelectionOfDocument();

  // 3. Let anchor be the boundary point (anchorNode, anchorOffset) and let
  // focus be the boundary point (focusNode, focusOffset).
  Position base_position(base_node, base_offset);
  Position extent_position(extent_node, extent_offset);
  // 4. Let newRange be a new range.
  Range* new_range = Range::Create(base_node->GetDocument());
  // 5. If anchor is before focus, set the start the newRange's start to anchor
  // and its end to focus. Otherwise, set the start them to focus and anchor
  // respectively.
  if (extent_position.IsNull()) {
    new_range->setStart(base_node, base_offset);
    new_range->setEnd(base_node, base_offset);
  } else if (base_position < extent_position) {
    new_range->setStart(base_node, base_offset);
    new_range->setEnd(extent_node, extent_offset);
  } else {
    new_range->setStart(extent_node, extent_offset);
    new_range->setEnd(base_node, base_offset);
  }
  // 6. Set this's range to newRange.
  UpdateFrameSelection(
      SelectionInDomTree::Builder()
          .SetBaseAndExtentDeprecated(base_position, extent_position)
          .Build(),
      new_range, SetSelectionOptions::Builder().SetIsDirectional(true).Build());
}

void DomSelection::modify(const String& alter_string,
                          const String& direction_string,
                          const String& granularity_string) {
  if (!IsAvailable())
    return;

  SelectionModifyAlteration alter;
  if (EqualIgnoringAsciiCase(alter_string, "extend")) {
    alter = SelectionModifyAlteration::kExtend;
  } else if (EqualIgnoringAsciiCase(alter_string, "move")) {
    alter = SelectionModifyAlteration::kMove;
  } else {
    return;
  }

  SelectionModifyDirection direction;
  if (EqualIgnoringAsciiCase(direction_string, "forward")) {
    direction = SelectionModifyDirection::kForward;
  } else if (EqualIgnoringAsciiCase(direction_string, "backward")) {
    direction = SelectionModifyDirection::kBackward;
  } else if (EqualIgnoringAsciiCase(direction_string, "left")) {
    direction = SelectionModifyDirection::kLeft;
  } else if (EqualIgnoringAsciiCase(direction_string, "right")) {
    direction = SelectionModifyDirection::kRight;
  } else {
    return;
  }

  TextGranularity granularity;
  if (EqualIgnoringAsciiCase(granularity_string, "character")) {
    granularity = TextGranularity::kCharacter;
  } else if (EqualIgnoringAsciiCase(granularity_string, "word")) {
    granularity = TextGranularity::kWord;
  } else if (EqualIgnoringAsciiCase(granularity_string, "sentence")) {
    granularity = TextGranularity::kSentence;
  } else if (EqualIgnoringAsciiCase(granularity_string, "line")) {
    granularity = TextGranularity::kLine;
  } else if (EqualIgnoringAsciiCase(granularity_string, "paragraph")) {
    granularity = TextGranularity::kParagraph;
  } else if (EqualIgnoringAsciiCase(granularity_string, "lineboundary")) {
    granularity = TextGranularity::kLineBoundary;
  } else if (EqualIgnoringAsciiCase(granularity_string, "sentenceboundary")) {
    granularity = TextGranularity::kSentenceBoundary;
  } else if (EqualIgnoringAsciiCase(granularity_string, "paragraphboundary")) {
    granularity = TextGranularity::kParagraphBoundary;
  } else if (EqualIgnoringAsciiCase(granularity_string, "documentboundary")) {
    granularity = TextGranularity::kDocumentBoundary;
  } else {
    return;
  }

  // TODO(editing-dev): The use of UpdateStyleAndLayout
  // needs to be audited.  See http://crbug.com/590369 for more details.
  DomWindow()->document()->UpdateStyleAndLayout(
      DocumentUpdateReason::kSelection);

  Element* focused_element = DomWindow()->document()->FocusedElement();
  Selection().Modify(alter, direction, granularity, SetSelectionBy::kSystem);
  if (DomWindow() &&
      focused_element != DomWindow()->document()->FocusedElement()) {
    UseCounter::Count(DomWindow(), WebFeature::kSelectionFuncionsChangeFocus);
  }
}

// https://www.w3.org/TR/selection-api/#dom-selection-extend
void DomSelection::extend(Node* node,
                          wtf_size_t offset,
                          ExceptionState& exception_state) {
  DCHECK(node);
  if (!IsAvailable())
    return;

  // 1. If the document associated with this is not a shadow-including
  // inclusive ancestor of node, abort these steps.
  if (!IsValidForPosition(node))
    return;

  // 2. If the context object is empty, throw an InvalidStateError exception and
  // abort these steps.
  if (rangeCount() == 0) {
    exception_state.ThrowDOMException(
        DOMExceptionCode::kInvalidStateError,
        "This Selection object doesn't have any Ranges.");
    return;
  }

  Range::CheckNodeWOffset(node, offset, exception_state);
  if (exception_state.HadException())
    return;

  // 3. Let oldAnchor and oldFocus be the context object's anchor and focus, and
  // let newFocus be the boundary point (node, offset).
  const Position old_anchor =
      Selection().GetSelectionInDomTree().Anchor().ToOffsetInAnchor();

  DCHECK(!old_anchor.IsNull());
  const Position new_focus(node, offset);

  ClearCachedRangeIfSelectionOfDocument();

  // 4. Let newRange be a new range.
  Range* new_range = Range::Create(*DomWindow()->document());

  // 5. If node's root is not the same as the context object's range's root, set
  // newRange's start and end to newFocus.
  // E.g. oldAnchor might point in shadow Text node in TextControlElement.
  if (old_anchor.AnchorNode()->TreeRoot() != node->TreeRoot()) {
    new_range->setStart(node, offset);
    new_range->setEnd(node, offset);

  } else if (old_anchor <= new_focus) {
    // 6. Otherwise, if oldAnchor is before or equal to newFocus, set newRange's
    // start to oldAnchor, then set its end to newFocus.
    new_range->setStart(old_anchor.AnchorNode(),
                        old_anchor.OffsetInContainerNode());
    new_range->setEnd(node, offset);

  } else {
    // 7. Otherwise, set newRange's start to newFocus, then set its end to
    // oldAnchor.
    new_range->setStart(node, offset);
    new_range->setEnd(old_anchor.AnchorNode(),
                      old_anchor.OffsetInContainerNode());
  }

  // 8. Set the context object's range to newRange.
  SelectionInDomTree::Builder builder;
  if (new_range->collapsed())
    builder.Collapse(new_focus);
  else
    builder.Collapse(old_anchor).Extend(new_focus);
  UpdateFrameSelection(
      builder.Build(), new_range,
      SetSelectionOptions::Builder().SetIsDirectional(true).Build());
}

Range* DomSelection::getRangeAt(wtf_size_t index,
                                ExceptionState& exception_state) const {
  if (!IsAvailable())
    return nullptr;

  if (index >= rangeCount()) {
    exception_state.ThrowDOMException(
        DOMExceptionCode::kIndexSizeError,
        StrCat({String::Number(index), " is not a valid index."}));
    return nullptr;
  }

  // If you're hitting this, you've added broken multi-range selection support
  DCHECK_EQ(rangeCount(), 1u);

  if (Range* cached_range = DocumentCachedRange())
    return cached_range;

  Range* range = CreateRange(CreateRangeFromSelectionEditor());
  CacheRangeIfSelectionOfDocument(range);
  return range;
}

// https://www.w3.org/TR/selection-api/#dom-selection-getcomposedranges
const StaticRangeVector DomSelection::getComposedRanges(
    const GetComposedRangesOptions* options) const {
  StaticRangeVector ranges;
  // 1. If this is empty, return an empty array.
  if (!IsAvailable()) {
    return ranges;
  }
  TemporaryRange temp_range(this, PrimaryRangeOrNull());
  if (!temp_range.GetRange()) {
    return ranges;
  }

  const SelectionInDomTree& selection = Selection().GetSelectionInDomTree();
  // 2. Otherwise, let startNode be start node of the range associated with
  // this, and let startOffset be start offset of the range.
  // 3. Rescope startNode and startOffset with listed shadow roots.
  Position start =
      Rescope(selection.ComputeStartPosition(), options->shadowRoots(),
              /*is_end=*/false);

  // 4. Let endNode be end node of the range associated with this, and let
  // endOffset be end offset of the range.
  // 5. Rescope endNode and endOffset with listed shadow roots.
  Position end = Rescope(selection.ComputeEndPosition(), options->shadowRoots(),
                         /*is_end=*/true);

  // 6. Return an array consisting of new StaticRange whose start node is
  // startNode, start offset is startOffset, end node is endNode, and end
  // offset is endOffset.
  ranges.push_back(MakeGarbageCollected<StaticRange>(
      start.ComputeContainerNode(), start.ComputeOffsetInContainerNode(),
      end.ComputeContainerNode(), end.ComputeOffsetInContainerNode()));
  return ranges;
}

// If isEnd is false, rescope following spec step 3.
// Else, Rescope following sepc step 5.
// https://www.w3.org/TR/selection-api/#dom-selection-getcomposedranges
Position DomSelection::Rescope(
    const Position& position,
    const HeapVector<Member<ShadowRoot>>& shadow_roots,
    bool is_end) const {
  if (position.IsNull()) {
    return Position();
  }
  Node* node = position.ComputeContainerNode();
  wtf_size_t offset = position.ComputeOffsetInContainerNode();
  // 3. & 5. While node is a node, node's root is a shadow root, and
  // node's root is not a shadow-including inclusive ancestor of any of
  // shadowRoots, repeat these steps:
  while (node) {
    ShadowRoot* root = node->ContainingShadowRoot();
    Element* host = node->OwnerShadowHost();
    if (!root || !host) {
      return Position(node, offset);
    }
    for (auto& shadowRoot : shadow_roots) {
      if (root->IsShadowIncludingInclusiveAncestorOf(*shadowRoot)) {
        return Position(node, offset);
      }
    }
    // 1. Set node to node's root's host's parent.
    node = host->parentNode();
    // 2. Set offset to index of node's root's host.
    offset = host->NodeIndex();
    if (is_end) {
      offset += 1;
    }
  }
  return Position(node, offset);
}

Range* DomSelection::PrimaryRangeOrNull() const {
  return rangeCount() > 0 ? getRangeAt(0, ASSERT_NO_EXCEPTION) : nullptr;
}

EphemeralRange DomSelection::CreateRangeFromSelectionEditor() const {
  const VisibleSelection& selection = GetVisibleSelection();
  const Position& anchor = selection.Anchor().ParentAnchoredEquivalent();
  if (IsSelectionOfDocument() && !anchor.AnchorNode()->IsInShadowTree())
    return FirstEphemeralRangeOf(selection);

  Node* const anchor_node = ShadowAdjustedNode(anchor);
  if (!anchor_node)  // crbug.com/595100
    return EphemeralRange();

  const Position& focus = selection.Focus().ParentAnchoredEquivalent();
  const Position shadow_adjusted_focus =
      Position(ShadowAdjustedNode(focus), ShadowAdjustedOffset(focus));
  const Position shadow_adjusted_anchor =
      Position(anchor_node, ShadowAdjustedOffset(anchor));
  if (selection.IsAnchorFirst()) {
    return EphemeralRange(shadow_adjusted_anchor, shadow_adjusted_focus);
  }
  return EphemeralRange(shadow_adjusted_focus, shadow_adjusted_anchor);
}

bool DomSelection::IsSelectionOfDocument() const {
  return tree_scope_ == tree_scope_->GetDocument();
}

void DomSelection::CacheRangeIfSelectionOfDocument(Range* range) const {
  if (!IsSelectionOfDocument())
    return;
  if (!DomWindow())
    return;
  Selection().CacheRangeOfDocument(range);
}

Range* DomSelection::DocumentCachedRange() const {
  return IsSelectionOfDocument() ? Selection().DocumentCachedRange() : nullptr;
}

void DomSelection::ClearCachedRangeIfSelectionOfDocument() {
  if (IsSelectionOfDocument())
    Selection().ClearDocumentCachedRange();
}

void DomSelection::removeRange(Range* range, ExceptionState& exception_state) {
  DCHECK(range);
  TemporaryRange temp_range(this, PrimaryRangeOrNull());
  if (IsAvailable() && range == temp_range.GetRange()) {
    Selection().Clear();
  } else {
    if (RuntimeEnabledFeatures::SelectionRemoveRangeNotFoundErrorEnabled()) {
      exception_state.ThrowDOMException(DOMExceptionCode::kNotFoundError,
                                        "Range not found.");
    }
  }
}

void DomSelection::removeAllRanges() {
  if (IsAvailable())
    Selection().Clear();
}

void DomSelection::addRange(Range* new_range) {
  DCHECK(new_range);

  if (!IsAvailable())
    return;

  if (new_range->OwnerDocument() != DomWindow()->document())
    return;

  if (!new_range->IsConnected()) {
    AddConsoleWarning("addRange(): The given range isn't in document.");
    return;
  }

  if (new_range->OwnerDocument() != Selection().GetDocument()) {
    // "editing/selection/selection-in-iframe-removed-crash.html" goes here.
    return;
  }

  if (rangeCount() == 0) {
    UpdateFrameSelection(SelectionInDomTree::Builder()
                             .Collapse(new_range->StartPosition())
                             .Extend(new_range->EndPosition())
                             .Build(),
                         new_range, SetSelectionOptions());
    return;
  }
}

// https://www.w3.org/TR/selection-api/#dom-selection-deletefromdocument
void DomSelection::deleteFromDocument() {
  if (!IsAvailable())
    return;

  // The method must invoke deleteContents() ([DOM4]) on the context object's
  // range if the context object is not empty. Otherwise the method must do
  // nothing.
  if (Range* range = DocumentCachedRange()) {
    range->deleteContents(ASSERT_NO_EXCEPTION);
    return;
  }

  // TODO(editing-dev): The use of UpdateStyleAndLayout
  // needs to be audited.  See http://crbug.com/590369 for more details.
  DomWindow()->document()->UpdateStyleAndLayout(
      DocumentUpdateReason::kSelection);

  Range* selected_range = CreateRange(Selection()
                                          .ComputeVisibleSelectionInDomTree()
                                          .ToNormalizedEphemeralRange());
  if (!selected_range)
    return;
  if (selected_range->startContainer()->IsInUserAgentShadowRoot()) {
    return;
  }

  // |selectedRange| may point nodes in a different root.
  selected_range->deleteContents(ASSERT_NO_EXCEPTION);
}

bool DomSelection::containsNode(const Node* n, bool allow_partial) const {
  DCHECK(n);

  if (!IsAvailable())
    return false;

  if (DomWindow()->document() != n->GetDocument())
    return false;

  wtf_size_t node_index = n->NodeIndex();

  // TODO(editing-dev): The use of UpdateStyleAndLayout
  // needs to be audited.  See http://crbug.com/590369 for more details.
  // |VisibleSelection::toNormalizedEphemeralRange| requires clean layout.
  DomWindow()->document()->UpdateStyleAndLayout(
      DocumentUpdateReason::kSelection);

  const EphemeralRange selected_range = Selection()
                                            .ComputeVisibleSelectionInDomTree()
                                            .ToNormalizedEphemeralRange();
  if (selected_range.IsNull())
    return false;

  ContainerNode* parent_node = n->parentNode();
  if (!parent_node)
    return false;

  const Position start_position =
      selected_range.StartPosition().ToOffsetInAnchor();
  const Position end_position = selected_range.EndPosition().ToOffsetInAnchor();
  DummyExceptionStateForTesting exception_state;
  bool node_fully_selected =
      Range::compareBoundaryPoints(
          parent_node, node_index, start_position.ComputeContainerNode(),
          start_position.OffsetInContainerNode(), exception_state) >= 0 &&
      !exception_state.HadException() &&
      Range::compareBoundaryPoints(
          parent_node, node_index + 1, end_position.ComputeContainerNode(),
          end_position.OffsetInContainerNode(), exception_state) <= 0 &&
      !exception_state.HadException();
  if (exception_state.HadException())
    return false;
  if (node_fully_selected)
    return true;

  bool node_fully_unselected =
      (Range::compareBoundaryPoints(
           parent_node, node_index, end_position.ComputeContainerNode(),
           end_position.OffsetInContainerNode(), exception_state) > 0 &&
       !exception_state.HadException()) ||
      (Range::compareBoundaryPoints(
           parent_node, node_index + 1, start_position.ComputeContainerNode(),
           start_position.OffsetInContainerNode(), exception_state) < 0 &&
       !exception_state.HadException());
  DCHECK(!exception_state.HadException());
  if (node_fully_unselected)
    return false;

  return allow_partial || n->IsTextNode();
}

void DomSelection::selectAllChildren(Node* n, ExceptionState& exception_state) {
  DCHECK(n);

  // This doesn't (and shouldn't) select text node characters.
  setBaseAndExtent(n, 0, n, n->CountChildren(), exception_state);
}

String DomSelection::toString() {
  if (!IsAvailable())
    return String();

  // TODO(editing-dev): The use of UpdateStyleAndLayout
  // needs to be audited.  See http://crbug.com/590369 for more details.
  DomWindow()->document()->UpdateStyleAndLayout(
      DocumentUpdateReason::kSelection);

  DocumentLifecycle::DisallowTransitionScope disallow_transition(
      DomWindow()->document()->Lifecycle());

  const EphemeralRange range = Selection()
                                   .ComputeVisibleSelectionInDomTree()
                                   .ToNormalizedEphemeralRange();

  TextIteratorBehavior::Builder behavior_builder;
  behavior_builder.SetForSelectionToString(true);
  behavior_builder.SetSkipsUnselectableContent(true);

  return PlainText(range, behavior_builder.Build());
}

Node* DomSelection::ShadowAdjustedNode(const Position& position) const {
  if (position.IsNull())
    return nullptr;

  Node* container_node = position.ComputeContainerNode();
  Node* adjusted_node = tree_scope_->AncestorInThisScope(container_node);

  if (!adjusted_node)
    return nullptr;

  if (container_node == adjusted_node)
    return container_node;

  DCHECK(!adjusted_node->IsShadowRoot()) << adjusted_node;
  return adjusted_node->ParentOrShadowHostNode();
}

wtf_size_t DomSelection::ShadowAdjustedOffset(const Position& position) const {
  if (position.IsNull())
    return 0;

  Node* container_node = position.ComputeContainerNode();
  Node* adjusted_node = tree_scope_->AncestorInThisScope(container_node);

  if (!adjusted_node)
    return 0;

  if (container_node == adjusted_node)
    return position.ComputeOffsetInContainerNode();

  return adjusted_node->NodeIndex();
}

bool DomSelection::IsValidForPosition(Node* node) const {
  DCHECK(DomWindow());
  if (!node)
    return true;
  return node->GetDocument() == DomWindow()->document() && node->isConnected();
}

void DomSelection::AddConsoleWarning(const String& message) {
  if (tree_scope_) {
    tree_scope_->GetDocument().AddConsoleMessage(
        MakeGarbageCollected<ConsoleMessage>(
            mojom::ConsoleMessageSource::kJavaScript,
            mojom::ConsoleMessageLevel::kWarning, message));
  }
}

void DomSelection::Trace(Visitor* visitor) const {
  visitor->Trace(tree_scope_);
  ScriptWrappable::Trace(visitor);
  ExecutionContextClient::Trace(visitor);
}

DomSelection::TemporaryRange::TemporaryRange(const DomSelection* selection,
                                             Range* range) {
  owner_dom_selection_ = selection;
  range_ = range;
}

DomSelection::TemporaryRange::~TemporaryRange() {
  if (range_ && range_ != owner_dom_selection_->DocumentCachedRange()) {
    range_->Dispose();
  }
}

Range* DomSelection::TemporaryRange::GetRange() {
  return range_;
}

}  // namespace blink