bool selectionBelongsToObject(AccessibilityObject* coreObject, VisibleSelection& selection)
{
    if (!coreObject || !coreObject->isAccessibilityRenderObject())
        return false;

    if (selection.isNone())
        return false;

    RefPtr<Range> range = selection.toNormalizedRange();
    if (!range)
        return false;

    // We want to check that both the selection intersects the node
    // AND that the selection is not just "touching" one of the
    // boundaries for the selected node. We want to check whether the
    // node is actually inside the region, at least partially.
    auto& node = *coreObject->node();
    auto* lastDescendant = node.lastDescendant();
    unsigned lastOffset = lastOffsetInNode(lastDescendant);
    auto intersectsResult = range->intersectsNode(node);
    return !intersectsResult.hasException()
           && intersectsResult.releaseReturnValue()
           && (&range->endContainer() != &node || range->endOffset())
           && (&range->startContainer() != lastDescendant || range->startOffset() != lastOffset);
}

RefPtr<TextIndicator> TextIndicator::createWithRange(const Range& range, TextIndicatorPresentationTransition presentationTransition, unsigned margin)
{
    Frame* frame = range.startContainer()->document().frame();

    if (!frame)
        return nullptr;

#if PLATFORM(IOS)
    frame->editor().setIgnoreCompositionSelectionChange(true);
    frame->selection().setUpdateAppearanceEnabled(true);
#endif

    VisibleSelection oldSelection = frame->selection().selection();
    frame->selection().setSelection(range);

    RefPtr<TextIndicator> indicator = TextIndicator::createWithSelectionInFrame(*frame, presentationTransition, margin);

    frame->selection().setSelection(oldSelection);

    if (indicator)
        indicator->setWantsMargin(!areRangesEqual(&range, oldSelection.toNormalizedRange().get()));

#if PLATFORM(IOS)
    frame->editor().setIgnoreCompositionSelectionChange(false, Editor::RevealSelection::No);
    frame->selection().setUpdateAppearanceEnabled(false);
#endif

    return indicator.release();
}

bool Editor::insertTextWithoutSendingTextEvent(const String& text, bool selectInsertedText, TextEvent* triggeringEvent)
{
    if (text.isEmpty())
        return false;

    VisibleSelection selection = selectionForCommand(triggeringEvent);
    if (!selection.isContentEditable())
        return false;

    spellChecker().updateMarkersForWordsAffectedByEditing(isSpaceOrNewline(text[0]));

    // Get the selection to use for the event that triggered this insertText.
    // If the event handler changed the selection, we may want to use a different selection
    // that is contained in the event target.
    selection = selectionForCommand(triggeringEvent);
    if (selection.isContentEditable()) {
        if (Node* selectionStart = selection.start().deprecatedNode()) {
            RefPtr<Document> document(selectionStart->document());

            // Insert the text
            TypingCommand::Options options = 0;
            if (selectInsertedText)
                options |= TypingCommand::SelectInsertedText;
            TypingCommand::insertText(*document.get(), text, selection, options, triggeringEvent && triggeringEvent->isComposition() ? TypingCommand::TextCompositionConfirm : TypingCommand::TextCompositionNone);

            // Reveal the current selection
            if (LocalFrame* editedFrame = document->frame()) {
                if (Page* page = editedFrame->page())
                    page->focusController().focusedOrMainFrame()->selection().revealSelection(ScrollAlignment::alignCenterIfNeeded);
            }
        }
    }

    return true;
}

bool static selectionIsContainedByAnchorNode(const VisibleSelection& selection)
{
    // Check whether the start or end of the selection is outside of the selections
    // anchor node.
    return (selection.start().anchorType() == WebCore::Position::PositionIsOffsetInAnchor
            && selection.end().anchorType() == WebCore::Position::PositionIsOffsetInAnchor);
}

// Updates |selectionInFlatTree| to match with |selection|.
void SelectionAdjuster::adjustSelectionInFlatTree(
    VisibleSelectionInFlatTree* selectionInFlatTree,
    const VisibleSelection& selection) {
  if (selection.isNone()) {
    *selectionInFlatTree = VisibleSelectionInFlatTree();
    return;
  }

  const PositionInFlatTree& base = toPositionInFlatTree(selection.base());
  const PositionInFlatTree& extent = toPositionInFlatTree(selection.extent());
  const PositionInFlatTree& position1 = toPositionInFlatTree(selection.start());
  const PositionInFlatTree& position2 = toPositionInFlatTree(selection.end());
  position1.anchorNode()->updateDistribution();
  position2.anchorNode()->updateDistribution();
  selectionInFlatTree->m_base = base;
  selectionInFlatTree->m_extent = extent;
  selectionInFlatTree->m_affinity = selection.m_affinity;
  selectionInFlatTree->m_isDirectional = selection.m_isDirectional;
  selectionInFlatTree->m_granularity = selection.m_granularity;
  selectionInFlatTree->m_hasTrailingWhitespace =
      selection.m_hasTrailingWhitespace;
  selectionInFlatTree->m_baseIsFirst =
      base.isNull() || base.compareTo(extent) <= 0;
  if (position1.compareTo(position2) <= 0) {
    selectionInFlatTree->m_start = position1;
    selectionInFlatTree->m_end = position2;
  } else {
    selectionInFlatTree->m_start = position2;
    selectionInFlatTree->m_end = position1;
  }
  selectionInFlatTree->updateSelectionType();
}

static String selectMisspellingAsync(Frame* selectedFrame, DocumentMarker& marker)
{
    VisibleSelection selection = selectedFrame->selection()->selection();
    if (!selection.isCaretOrRange())
        return String();

    // Caret and range selections always return valid normalized ranges.
    RefPtr<Range> selectionRange = selection.toNormalizedRange();
    Vector<DocumentMarker*> markers = selectedFrame->document()->markers()->markersInRange(selectionRange.get(), DocumentMarker::Spelling | DocumentMarker::Grammar);
    if (markers.size() != 1)
        return String();
    marker = *markers[0];

    // Cloning a range fails only for invalid ranges.
    RefPtr<Range> markerRange = selectionRange->cloneRange(ASSERT_NO_EXCEPTION);
    markerRange->setStart(markerRange->startContainer(), marker.startOffset());
    markerRange->setEnd(markerRange->endContainer(), marker.endOffset());
    if (selection.isCaret()) {
        selection = VisibleSelection(markerRange.get());
        selectedFrame->selection()->setSelection(selection, WordGranularity);
        selectionRange = selection.toNormalizedRange();
    }

    if (markerRange->text().stripWhiteSpace(&IsWhiteSpaceOrPunctuation) != selectionRange->text().stripWhiteSpace(&IsWhiteSpaceOrPunctuation))
        return String();

    return markerRange->text();
}

static void expandSelectionToGranularity(Frame* frame, int x, int y, TextGranularity granularity, bool isInputMode)
{
    ASSERT(frame);
    ASSERT(frame->selection());

    VisibleSelection selection;
    if (x < 0 || y < 0) {
        if (!isInputMode)
            return; // Invalid request

        // Input mode based selection, use the current selection as the selection point.
        ASSERT(frame->selection()->selectionType() != VisibleSelection::NoSelection);
        selection = frame->selection()->selection();
    } else {
        VisiblePosition pointLocation(frame->visiblePositionForPoint(WebCore::IntPoint(x, y)));
        selection = VisibleSelection(pointLocation, pointLocation);
    }

    if (!(selection.start().anchorNode() && selection.start().anchorNode()->isTextNode()))
        return;

    selection.expandUsingGranularity(granularity);
    RefPtr<Range> newRange = selection.toNormalizedRange();
    if (!newRange)
        return;
    ExceptionCode ec = 0;
    if (newRange->collapsed(ec))
        return;
    RefPtr<Range> oldRange = frame->selection()->selection().toNormalizedRange();
    EAffinity affinity = frame->selection()->affinity();
    if (isInputMode && !frame->editor()->client()->shouldChangeSelectedRange(oldRange.get(), newRange.get(), affinity, false))
        return;
    frame->selection()->setSelectedRange(newRange.get(), affinity, true);
}

static bool isTextWithCaret(AccessibilityObject* coreObject)
{
    if (!coreObject || !coreObject->isAccessibilityRenderObject())
        return false;

    Document* document = coreObject->document();
    if (!document)
        return false;

    Frame* frame = document->frame();
    if (!frame)
        return false;

    if (!frame->settings().caretBrowsingEnabled())
        return false;

    // Check text objects and paragraphs only.
    AtkObject* axObject = coreObject->wrapper();
    AtkRole role = axObject ? atk_object_get_role(axObject) : ATK_ROLE_INVALID;
    if (role != ATK_ROLE_TEXT && role != ATK_ROLE_PARAGRAPH)
        return false;

    // Finally, check whether the caret is set in the current object.
    VisibleSelection selection = coreObject->selection();
    if (!selection.isCaret())
        return false;

    return selectionBelongsToObject(coreObject, selection);
}

VisibleSelection PendingSelection::calcVisibleSelectionAlgorithm() const
{
    using PositionType = typename Strategy::PositionType;

    PositionType start = Strategy::selectionStart(m_selection);
    PositionType end = Strategy::selectionEnd(m_selection);
    SelectionType selectionType = VisibleSelection::selectionType(start, end);
    TextAffinity affinity = m_selection.affinity();

    bool paintBlockCursor = m_shouldShowBlockCursor && selectionType == SelectionType::CaretSelection && !isLogicalEndOfLine(VisiblePosition(end, affinity));
    VisibleSelection selection;
    if (enclosingTextFormControl(start.computeContainerNode())) {
        // TODO(yosin) We should use |PositionMoveType::Character| to avoid
        // ending paint at middle of character.
        PositionType endPosition = paintBlockCursor ? nextPositionOf(Strategy::selectionExtent(m_selection), PositionMoveType::CodePoint) : end;
        selection.setWithoutValidation(start, endPosition);
        return selection;
    }

    VisiblePosition visibleStart = VisiblePosition(start, selectionType == SelectionType::RangeSelection ? TextAffinity::Downstream : affinity);
    if (paintBlockCursor) {
        VisiblePosition visibleExtent(end, affinity);
        visibleExtent = visibleExtent.next(CanSkipOverEditingBoundary);
        return VisibleSelection(visibleStart, visibleExtent);
    }
    VisiblePosition visibleEnd(end, selectionType == SelectionType::RangeSelection ? TextAffinity::Upstream : affinity);
    return VisibleSelection(visibleStart, visibleEnd);
}

// This avoids the expense of a full fledged delete operation, and avoids a layout that typically results
// from text removal.
bool InsertTextCommand::performTrivialReplace(const String& text, bool selectInsertedText)
{
    if (!endingSelection().isRange())
        return false;
    
    if (text.contains('\t') || text.contains(' ') || text.contains('\n'))
        return false;
    
    Position start = endingSelection().start();
    Position end = endingSelection().end();
    
    if (start.node() != end.node() || !start.node()->isTextNode() || isTabSpanTextNode(start.node()))
        return false;
        
    replaceTextInNode(static_cast<Text*>(start.node()), start.deprecatedEditingOffset(), end.deprecatedEditingOffset() - start.deprecatedEditingOffset(), text);
    
    Position endPosition(start.node(), start.deprecatedEditingOffset() + text.length());
    
    // We could have inserted a part of composed character sequence,
    // so we are basically treating ending selection as a range to avoid validation.
    // <http://bugs.webkit.org/show_bug.cgi?id=15781>
    VisibleSelection forcedEndingSelection;
    forcedEndingSelection.setWithoutValidation(start, endPosition);
    setEndingSelection(forcedEndingSelection);
    
    if (!selectInsertedText)
        setEndingSelection(VisibleSelection(endingSelection().visibleEnd()));
    
    return true;
}

// This avoids the expense of a full fledged delete operation, and avoids a layout that typically results
// from text removal.
bool InsertTextCommand::performTrivialReplace(const String& text, bool selectInsertedText)
{
    if (!endingSelection().isRange())
        return false;
    
    if (text.contains('\t') || text.contains(' ') || text.contains('\n'))
        return false;

    Position start = endingSelection().start();
    Position endPosition = replaceSelectedTextInNode(text);
    if (endPosition.isNull())
        return false;

    // We could have inserted a part of composed character sequence,
    // so we are basically treating ending selection as a range to avoid validation.
    // <http://bugs.webkit.org/show_bug.cgi?id=15781>
    VisibleSelection forcedEndingSelection;
    forcedEndingSelection.setWithoutValidation(start, endPosition);
    forcedEndingSelection.setIsDirectional(endingSelection().isDirectional());
    setEndingSelection(forcedEndingSelection);

    if (!selectInsertedText)
        setEndingSelection(VisibleSelection(endingSelection().visibleEnd(), endingSelection().isDirectional()));
    
    return true;
}

void SpellChecker::markMisspellingsAfterTypingToWord(const VisiblePosition &wordStart, const VisibleSelection& selectionAfterTyping)
{
    if (unifiedTextCheckerEnabled()) {
        TextCheckingTypeMask textCheckingOptions = 0;

        if (isContinuousSpellCheckingEnabled())
            textCheckingOptions |= TextCheckingTypeSpelling;

        if (!(textCheckingOptions & TextCheckingTypeSpelling))
            return;

        if (isGrammarCheckingEnabled())
            textCheckingOptions |= TextCheckingTypeGrammar;

        VisibleSelection adjacentWords = VisibleSelection(startOfWord(wordStart, LeftWordIfOnBoundary), endOfWord(wordStart, RightWordIfOnBoundary));
        if (textCheckingOptions & TextCheckingTypeGrammar) {
            VisibleSelection selectedSentence = VisibleSelection(startOfSentence(wordStart), endOfSentence(wordStart));
            markAllMisspellingsAndBadGrammarInRanges(textCheckingOptions, adjacentWords.toNormalizedRange().get(), selectedSentence.toNormalizedRange().get());
        } else {
            markAllMisspellingsAndBadGrammarInRanges(textCheckingOptions, adjacentWords.toNormalizedRange().get(), adjacentWords.toNormalizedRange().get());
        }
        return;
    }

    if (!isContinuousSpellCheckingEnabled())
        return;

    // Check spelling of one word
    RefPtr<Range> misspellingRange = nullptr;
    markMisspellings(VisibleSelection(startOfWord(wordStart, LeftWordIfOnBoundary), endOfWord(wordStart, RightWordIfOnBoundary)), misspellingRange);

    // Autocorrect the misspelled word.
    if (!misspellingRange)
        return;

    // Get the misspelled word.
    const String misspelledWord = plainText(misspellingRange.get());
    String autocorrectedString = textChecker().getAutoCorrectSuggestionForMisspelledWord(misspelledWord);

    // If autocorrected word is non empty, replace the misspelled word by this word.
    if (!autocorrectedString.isEmpty()) {
        VisibleSelection newSelection(misspellingRange.get(), DOWNSTREAM);
        if (newSelection != m_frame.selection().selection()) {
            m_frame.selection().setSelection(newSelection);
        }

        m_frame.editor().replaceSelectionWithText(autocorrectedString, false, false);

        // Reset the charet one character further.
        m_frame.selection().moveTo(m_frame.selection().selection().visibleEnd());
        m_frame.selection().modify(FrameSelection::AlterationMove, DirectionForward, CharacterGranularity);
    }

    if (!isGrammarCheckingEnabled())
        return;

    // Check grammar of entire sentence
    markBadGrammar(VisibleSelection(startOfSentence(wordStart), endOfSentence(wordStart)));
}

VisibleSelection SurroundingTextTest::select(int start, int end)
{
    Element* element = document().getElementById("selection");
    VisibleSelection selection;
    selection.setBase(Position(toText(element->firstChild()), start));
    selection.setExtent(Position(toText(element->firstChild()), end));
    return selection;
}

void visibleTextQuads(const VisibleSelection& selection, Vector<FloatQuad>& quads)
{
    if (!selection.isRange())
        return;
    ASSERT(selection.firstRange());

    visibleTextQuads(*(selection.firstRange()), quads, true /* useSelectionHeight */);
}

void InsertTextCommand::setEndingSelectionWithoutValidation(const Position& startPosition, const Position& endPosition)
{
    // We could have inserted a part of composed character sequence,
    // so we are basically treating ending selection as a range to avoid validation.
    // <http://bugs.webkit.org/show_bug.cgi?id=15781>
    VisibleSelection forcedEndingSelection;
    forcedEndingSelection.setWithoutValidation(startPosition, endPosition);
    forcedEndingSelection.setIsDirectional(endingSelection().isDirectional());
    setEndingSelection(forcedEndingSelection);
}

void TypingCommand::postTextStateChangeNotificationForDeletion(const VisibleSelection& selection)
{
    if (!AXObjectCache::accessibilityEnabled())
        return;
    postTextStateChangeNotification(AXTextEditTypeDelete, AccessibilityObject::stringForVisiblePositionRange(selection), selection.start());
    VisiblePositionIndexRange range;
    range.startIndex.value = indexForVisiblePosition(selection.start(), range.startIndex.scope);
    range.endIndex.value = indexForVisiblePosition(selection.end(), range.endIndex.scope);
    composition()->setTextInsertedByUnapplyRange(range);
}

static char* webkitAccessibleTextGetWordForBoundary(AtkText* text, int offset, AtkTextBoundary boundaryType, GetTextRelativePosition textPosition, int* startOffset, int* endOffset)
{
    AccessibilityObject* coreObject = core(text);
    Document* document = coreObject->document();
    if (!document)
        return emptyTextSelectionAtOffset(0, startOffset, endOffset);

    Node* node = getNodeForAccessibilityObject(coreObject);
    if (!node)
        return emptyTextSelectionAtOffset(0, startOffset, endOffset);

    int actualOffset = atkOffsetToWebCoreOffset(text, offset);

    // Besides of the usual conversion from ATK offsets to WebCore offsets,
    // we need to consider the potential embedded objects that might have been
    // inserted in the text exposed through AtkText when calculating the offset.
    actualOffset -= numberOfReplacedElementsBeforeOffset(text, actualOffset);

    VisiblePosition caretPosition = coreObject->visiblePositionForIndex(actualOffset);
    VisibleSelection currentWord = wordAtPositionForAtkBoundary(coreObject, caretPosition, boundaryType);

    // Take into account other relative positions, if needed, by
    // calculating the new position that we would need to consider.
    VisiblePosition newPosition = caretPosition;
    switch (textPosition) {
    case GetTextPositionAt:
        break;

    case GetTextPositionBefore:
        // Early return if asking for the previous word while already at the beginning.
        if (isFirstVisiblePositionInNode(currentWord.visibleStart(), node))
            return emptyTextSelectionAtOffset(0, startOffset, endOffset);

        if (isStartOfLine(currentWord.end()))
            newPosition = currentWord.visibleStart().previous();
        else
            newPosition = startOfWord(currentWord.start(), LeftWordIfOnBoundary);
        break;

    case GetTextPositionAfter:
        // Early return if asking for the following word while already at the end.
        if (isLastVisiblePositionInNode(currentWord.visibleEnd(), node))
            return emptyTextSelectionAtOffset(accessibilityObjectLength(coreObject), startOffset, endOffset);

        if (isEndOfLine(currentWord.end()))
            newPosition = currentWord.visibleEnd().next();
        else
            newPosition = endOfWord(currentWord.end(), RightWordIfOnBoundary);
        break;

    default:
        ASSERT_NOT_REACHED();
    }

    // Determine the relevant word we are actually interested in
    // and calculate the ATK offsets for it, then return everything.
    VisibleSelection selectedWord = newPosition != caretPosition ? wordAtPositionForAtkBoundary(coreObject, newPosition, boundaryType) : currentWord;
    getSelectionOffsetsForObject(coreObject, selectedWord, *startOffset, *endOffset);
    return webkitAccessibleTextGetText(text, *startOffset, *endOffset);
}

void InputMethodController::selectComposition() const
{
    RefPtr<Range> range = compositionRange();
    if (!range)
        return;

    // The composition can start inside a composed character sequence, so we have to override checks.
    // See <http://bugs.webkit.org/show_bug.cgi?id=15781>
    VisibleSelection selection;
    selection.setWithoutValidation(range->startPosition(), range->endPosition());
    m_frame->selection().setSelection(selection, 0);
}

void InputMethodController::selectComposition() const
{
    const EphemeralRange range = compositionEphemeralRange();
    if (range.isNull())
        return;

    // The composition can start inside a composed character sequence, so we have to override checks.
    // See <http://bugs.webkit.org/show_bug.cgi?id=15781>
    VisibleSelection selection;
    selection.setWithoutValidation(range.startPosition(), range.endPosition());
    frame().selection().setSelection(selection, 0);
}

void visibleTextQuads(const VisibleSelection& selection, Vector<FloatQuad>& quads)
{
    if (!selection.isRange())
        return;

    // Make sure that both start and end have valid nodes associated otherwise
    // this can crash. See PR 220628.
    if (!selection.start().anchorNode() || !selection.end().anchorNode())
        return;

    visibleTextQuads(*(selection.firstRange()), quads, true /* useSelectionHeight */);
}