1/*
2 * Copyright (C) 2004, 2008, 2009, 2010 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 *    notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 *    notice, this list of conditions and the following disclaimer in the
11 *    documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "SelectionController.h"
28
29#include "CharacterData.h"
30#include "DeleteSelectionCommand.h"
31#include "Document.h"
32#include "Editor.h"
33#include "EditorClient.h"
34#include "Element.h"
35#include "EventHandler.h"
36#include "ExceptionCode.h"
37#include "FloatQuad.h"
38#include "FocusController.h"
39#include "Frame.h"
40#include "FrameTree.h"
41#include "FrameView.h"
42#include "GraphicsContext.h"
43#include "HTMLFormElement.h"
44#include "HTMLFrameElementBase.h"
45#include "HTMLInputElement.h"
46#include "HTMLNames.h"
47#include "HitTestRequest.h"
48#include "HitTestResult.h"
49#include "Page.h"
50#include "Range.h"
51#include "RenderLayer.h"
52#include "RenderTextControl.h"
53#include "RenderTheme.h"
54#include "RenderView.h"
55#include "RenderWidget.h"
56#include "SecureTextInput.h"
57#include "Settings.h"
58#include "TextIterator.h"
59#include "TypingCommand.h"
60#include "htmlediting.h"
61#include "visible_units.h"
62#ifdef ANDROID_ALLOW_TURNING_OFF_CARET
63#include "WebViewCore.h"
64#endif
65#include <stdio.h>
66#include <wtf/text/CString.h>
67
68#define EDIT_DEBUG 0
69
70namespace WebCore {
71
72using namespace HTMLNames;
73
74const int NoXPosForVerticalArrowNavigation = INT_MIN;
75
76SelectionController::SelectionController(Frame* frame, bool isDragCaretController)
77    : m_frame(frame)
78    , m_xPosForVerticalArrowNavigation(NoXPosForVerticalArrowNavigation)
79    , m_granularity(CharacterGranularity)
80    , m_caretBlinkTimer(this, &SelectionController::caretBlinkTimerFired)
81    , m_caretRectNeedsUpdate(true)
82    , m_absCaretBoundsDirty(true)
83    , m_isDragCaretController(isDragCaretController)
84    , m_isCaretBlinkingSuspended(false)
85    , m_focused(frame && frame->page() && frame->page()->focusController()->focusedFrame() == frame)
86    , m_caretVisible(isDragCaretController)
87    , m_caretPaint(true)
88{
89    setIsDirectional(false);
90}
91
92void SelectionController::moveTo(const VisiblePosition &pos, bool userTriggered, CursorAlignOnScroll align)
93{
94    SetSelectionOptions options = CloseTyping | ClearTypingStyle;
95    if (userTriggered)
96        options |= UserTriggered;
97    setSelection(VisibleSelection(pos.deepEquivalent(), pos.deepEquivalent(), pos.affinity()), options, align);
98}
99
100void SelectionController::moveTo(const VisiblePosition &base, const VisiblePosition &extent, bool userTriggered)
101{
102    SetSelectionOptions options = CloseTyping | ClearTypingStyle;
103    if (userTriggered)
104        options |= UserTriggered;
105    setSelection(VisibleSelection(base.deepEquivalent(), extent.deepEquivalent(), base.affinity()), options);
106}
107
108void SelectionController::moveTo(const Position &pos, EAffinity affinity, bool userTriggered)
109{
110    SetSelectionOptions options = CloseTyping | ClearTypingStyle;
111    if (userTriggered)
112        options |= UserTriggered;
113    setSelection(VisibleSelection(pos, affinity), options);
114}
115
116void SelectionController::moveTo(const Range *r, EAffinity affinity, bool userTriggered)
117{
118    SetSelectionOptions options = CloseTyping | ClearTypingStyle;
119    if (userTriggered)
120        options |= UserTriggered;
121    VisibleSelection selection = r ? VisibleSelection(r->startPosition(), r->endPosition(), affinity) : VisibleSelection(Position(), Position(), affinity);
122    setSelection(selection, options);
123}
124
125void SelectionController::moveTo(const Position &base, const Position &extent, EAffinity affinity, bool userTriggered)
126{
127    SetSelectionOptions options = CloseTyping | ClearTypingStyle;
128    if (userTriggered)
129        options |= UserTriggered;
130    setSelection(VisibleSelection(base, extent, affinity), options);
131}
132
133void SelectionController::setSelection(const VisibleSelection& s, SetSelectionOptions options, CursorAlignOnScroll align, TextGranularity granularity, DirectionalityPolicy directionalityPolicy)
134{
135    m_granularity = granularity;
136
137    bool closeTyping = options & CloseTyping;
138    bool shouldClearTypingStyle = options & ClearTypingStyle;
139    bool userTriggered = options & UserTriggered;
140
141    setIsDirectional(directionalityPolicy == MakeDirectionalSelection);
142
143    if (m_isDragCaretController) {
144        invalidateCaretRect();
145        m_selection = s;
146        m_caretRectNeedsUpdate = true;
147        invalidateCaretRect();
148        updateCaretRect();
149        return;
150    }
151    if (!m_frame) {
152        m_selection = s;
153        return;
154    }
155
156    // <http://bugs.webkit.org/show_bug.cgi?id=23464>: Infinite recursion at SelectionController::setSelection
157    // if document->frame() == m_frame we can get into an infinite loop
158    if (s.base().anchorNode()) {
159        Document* document = s.base().anchorNode()->document();
160        if (document && document->frame() && document->frame() != m_frame && document != m_frame->document()) {
161            document->frame()->selection()->setSelection(s, options);
162            return;
163        }
164    }
165
166    if (closeTyping)
167        TypingCommand::closeTyping(m_frame->editor()->lastEditCommand());
168
169    if (shouldClearTypingStyle)
170        clearTypingStyle();
171
172    if (m_selection == s) {
173        // Even if selection was not changed, selection offsets may have been changed.
174        notifyRendererOfSelectionChange(userTriggered);
175        return;
176    }
177
178    VisibleSelection oldSelection = m_selection;
179
180    m_selection = s;
181
182    m_caretRectNeedsUpdate = true;
183
184    if (!s.isNone())
185        setFocusedNodeIfNeeded();
186
187    updateAppearance();
188
189    // Always clear the x position used for vertical arrow navigation.
190    // It will be restored by the vertical arrow navigation code if necessary.
191    m_xPosForVerticalArrowNavigation = NoXPosForVerticalArrowNavigation;
192    selectFrameElementInParentIfFullySelected();
193    notifyRendererOfSelectionChange(userTriggered);
194    m_frame->editor()->respondToChangedSelection(oldSelection, options);
195    if (userTriggered) {
196        ScrollAlignment alignment;
197
198        if (m_frame->editor()->behavior().shouldCenterAlignWhenSelectionIsRevealed())
199            alignment = (align == AlignCursorOnScrollAlways) ? ScrollAlignment::alignCenterAlways : ScrollAlignment::alignCenterIfNeeded;
200        else
201            alignment = (align == AlignCursorOnScrollAlways) ? ScrollAlignment::alignTopAlways : ScrollAlignment::alignToEdgeIfNeeded;
202
203        revealSelection(alignment, true);
204    }
205
206    notifyAccessibilityForSelectionChange();
207    m_frame->document()->enqueueDocumentEvent(Event::create(eventNames().selectionchangeEvent, false, false));
208}
209
210static bool removingNodeRemovesPosition(Node* node, const Position& position)
211{
212    if (!position.anchorNode())
213        return false;
214
215    if (position.anchorNode() == node)
216        return true;
217
218    if (!node->isElementNode())
219        return false;
220
221    Element* element = static_cast<Element*>(node);
222    return element->contains(position.anchorNode()) || element->contains(position.anchorNode()->shadowAncestorNode());
223}
224
225void SelectionController::nodeWillBeRemoved(Node *node)
226{
227    if (isNone())
228        return;
229
230    // There can't be a selection inside a fragment, so if a fragment's node is being removed,
231    // the selection in the document that created the fragment needs no adjustment.
232    if (node && highestAncestor(node)->nodeType() == Node::DOCUMENT_FRAGMENT_NODE)
233        return;
234
235    respondToNodeModification(node, removingNodeRemovesPosition(node, m_selection.base()), removingNodeRemovesPosition(node, m_selection.extent()),
236        removingNodeRemovesPosition(node, m_selection.start()), removingNodeRemovesPosition(node, m_selection.end()));
237}
238
239void SelectionController::respondToNodeModification(Node* node, bool baseRemoved, bool extentRemoved, bool startRemoved, bool endRemoved)
240{
241    bool clearRenderTreeSelection = false;
242    bool clearDOMTreeSelection = false;
243
244    if (startRemoved || endRemoved) {
245        // FIXME: When endpoints are removed, we should just alter the selection, instead of blowing it away.
246        clearRenderTreeSelection = true;
247        clearDOMTreeSelection = true;
248    } else if (baseRemoved || extentRemoved) {
249        // The base and/or extent are about to be removed, but the start and end aren't.
250        // Change the base and extent to the start and end, but don't re-validate the
251        // selection, since doing so could move the start and end into the node
252        // that is about to be removed.
253        if (m_selection.isBaseFirst())
254            m_selection.setWithoutValidation(m_selection.start(), m_selection.end());
255        else
256            m_selection.setWithoutValidation(m_selection.end(), m_selection.start());
257    } else if (RefPtr<Range> range = m_selection.firstRange()) {
258        ExceptionCode ec = 0;
259        Range::CompareResults compareResult = range->compareNode(node, ec);
260        if (!ec && (compareResult == Range::NODE_BEFORE_AND_AFTER || compareResult == Range::NODE_INSIDE)) {
261            // If we did nothing here, when this node's renderer was destroyed, the rect that it
262            // occupied would be invalidated, but, selection gaps that change as a result of
263            // the removal wouldn't be invalidated.
264            // FIXME: Don't do so much unnecessary invalidation.
265            clearRenderTreeSelection = true;
266        }
267    }
268
269    if (clearRenderTreeSelection) {
270        RefPtr<Document> document = m_selection.start().anchorNode()->document();
271        document->updateStyleIfNeeded();
272        if (RenderView* view = toRenderView(document->renderer()))
273            view->clearSelection();
274    }
275
276    if (clearDOMTreeSelection)
277        setSelection(VisibleSelection(), 0);
278}
279
280enum EndPointType { EndPointIsStart, EndPointIsEnd };
281
282static bool shouldRemovePositionAfterAdoptingTextReplacement(Position& position, EndPointType type, CharacterData* node, unsigned offset, unsigned oldLength, unsigned newLength)
283{
284    if (!position.anchorNode() || position.anchorNode() != node || position.anchorType() != Position::PositionIsOffsetInAnchor)
285        return false;
286
287    ASSERT(position.offsetInContainerNode() >= 0);
288    unsigned positionOffset = static_cast<unsigned>(position.offsetInContainerNode());
289    if (positionOffset > offset && positionOffset < offset + oldLength)
290        return true;
291
292    // Adjust the offset if the position is after or at the end of the deleted contents (positionOffset >= offset + oldLength)
293    // to avoid having a stale offset except when the position is the end of selection and nothing is deleted, in which case,
294    // adjusting offset results in incorrectly extending the selection until the end of newly inserted contents.
295    if ((positionOffset > offset + oldLength) || (positionOffset == offset + oldLength && (type == EndPointIsStart || oldLength)))
296        position.moveToOffset(positionOffset - oldLength + newLength);
297
298    return false;
299}
300
301void SelectionController::textWillBeReplaced(CharacterData* node, unsigned offset, unsigned oldLength, unsigned newLength)
302{
303    // The fragment check is a performance optimization. See http://trac.webkit.org/changeset/30062.
304    if (isNone() || !node || highestAncestor(node)->nodeType() == Node::DOCUMENT_FRAGMENT_NODE)
305        return;
306
307    Position base = m_selection.base();
308    Position extent = m_selection.extent();
309    Position start = m_selection.start();
310    Position end = m_selection.end();
311    bool shouldRemoveBase = shouldRemovePositionAfterAdoptingTextReplacement(base, m_selection.isBaseFirst() ? EndPointIsStart : EndPointIsEnd, node, offset, oldLength, newLength);
312    bool shouldRemoveExtent = shouldRemovePositionAfterAdoptingTextReplacement(extent, m_selection.isBaseFirst() ? EndPointIsEnd : EndPointIsStart, node, offset, oldLength, newLength);
313    bool shouldRemoveStart = shouldRemovePositionAfterAdoptingTextReplacement(start, EndPointIsStart, node, offset, oldLength, newLength);
314    bool shouldRemoveEnd = shouldRemovePositionAfterAdoptingTextReplacement(end, EndPointIsEnd, node, offset, oldLength, newLength);
315
316    if ((base != m_selection.base() || extent != m_selection.extent() || start != m_selection.start() || end != m_selection.end())
317        && !shouldRemoveStart && !shouldRemoveEnd) {
318        VisibleSelection newSelection;
319        if (!shouldRemoveBase && !shouldRemoveExtent)
320            newSelection.setWithoutValidation(base, extent);
321        else {
322            if (newSelection.isBaseFirst())
323                newSelection.setWithoutValidation(start, end);
324            else
325                newSelection.setWithoutValidation(end, start);
326        }
327        m_frame->document()->updateLayout();
328        setSelection(newSelection, 0);
329        return;
330    }
331
332    respondToNodeModification(node, shouldRemoveBase, shouldRemoveExtent, shouldRemoveStart, shouldRemoveEnd);
333}
334
335void SelectionController::setIsDirectional(bool isDirectional)
336{
337    m_isDirectional = !m_frame || m_frame->editor()->behavior().shouldConsiderSelectionAsDirectional() || isDirectional;
338}
339
340TextDirection SelectionController::directionOfEnclosingBlock()
341{
342    return WebCore::directionOfEnclosingBlock(m_selection.extent());
343}
344
345void SelectionController::willBeModified(EAlteration alter, SelectionDirection direction)
346{
347    if (alter != AlterationExtend)
348        return;
349
350    Position start = m_selection.start();
351    Position end = m_selection.end();
352
353    bool baseIsStart = true;
354
355    if (m_isDirectional) {
356        // Make base and extent match start and end so we extend the user-visible selection.
357        // This only matters for cases where base and extend point to different positions than
358        // start and end (e.g. after a double-click to select a word).
359        if (m_selection.isBaseFirst())
360            baseIsStart = true;
361        else
362            baseIsStart = false;
363    } else {
364        switch (direction) {
365        case DirectionRight:
366            if (directionOfEnclosingBlock() == LTR)
367                baseIsStart = true;
368            else
369                baseIsStart = false;
370            break;
371        case DirectionForward:
372            baseIsStart = true;
373            break;
374        case DirectionLeft:
375            if (directionOfEnclosingBlock() == LTR)
376                baseIsStart = false;
377            else
378                baseIsStart = true;
379            break;
380        case DirectionBackward:
381            baseIsStart = false;
382            break;
383        }
384    }
385    if (baseIsStart) {
386        m_selection.setBase(start);
387        m_selection.setExtent(end);
388    } else {
389        m_selection.setBase(end);
390        m_selection.setExtent(start);
391    }
392}
393
394VisiblePosition SelectionController::positionForPlatform(bool isGetStart) const
395{
396    Settings* settings = m_frame ? m_frame->settings() : 0;
397    if (settings && settings->editingBehaviorType() == EditingMacBehavior)
398        return isGetStart ? m_selection.visibleStart() : m_selection.visibleEnd();
399    // Linux and Windows always extend selections from the extent endpoint.
400    // FIXME: VisibleSelection should be fixed to ensure as an invariant that
401    // base/extent always point to the same nodes as start/end, but which points
402    // to which depends on the value of isBaseFirst. Then this can be changed
403    // to just return m_sel.extent().
404    return m_selection.isBaseFirst() ? m_selection.visibleEnd() : m_selection.visibleStart();
405}
406
407VisiblePosition SelectionController::startForPlatform() const
408{
409    return positionForPlatform(true);
410}
411
412VisiblePosition SelectionController::endForPlatform() const
413{
414    return positionForPlatform(false);
415}
416
417VisiblePosition SelectionController::modifyExtendingRight(TextGranularity granularity)
418{
419    VisiblePosition pos(m_selection.extent(), m_selection.affinity());
420
421    // The difference between modifyExtendingRight and modifyExtendingForward is:
422    // modifyExtendingForward always extends forward logically.
423    // modifyExtendingRight behaves the same as modifyExtendingForward except for extending character or word,
424    // it extends forward logically if the enclosing block is LTR direction,
425    // but it extends backward logically if the enclosing block is RTL direction.
426    switch (granularity) {
427    case CharacterGranularity:
428        if (directionOfEnclosingBlock() == LTR)
429            pos = pos.next(CannotCrossEditingBoundary);
430        else
431            pos = pos.previous(CannotCrossEditingBoundary);
432        break;
433    case WordGranularity:
434        if (directionOfEnclosingBlock() == LTR)
435            pos = nextWordPosition(pos);
436        else
437            pos = previousWordPosition(pos);
438        break;
439    case LineBoundary:
440        if (directionOfEnclosingBlock() == LTR)
441            pos = modifyExtendingForward(granularity);
442        else
443            pos = modifyExtendingBackward(granularity);
444        break;
445    case SentenceGranularity:
446    case LineGranularity:
447    case ParagraphGranularity:
448    case SentenceBoundary:
449    case ParagraphBoundary:
450    case DocumentBoundary:
451        // FIXME: implement all of the above?
452        pos = modifyExtendingForward(granularity);
453        break;
454    case WebKitVisualWordGranularity:
455        break;
456    }
457    return pos;
458}
459
460VisiblePosition SelectionController::modifyExtendingForward(TextGranularity granularity)
461{
462    VisiblePosition pos(m_selection.extent(), m_selection.affinity());
463    switch (granularity) {
464    case CharacterGranularity:
465        pos = pos.next(CannotCrossEditingBoundary);
466        break;
467    case WordGranularity:
468        pos = nextWordPosition(pos);
469        break;
470    case SentenceGranularity:
471        pos = nextSentencePosition(pos);
472        break;
473    case LineGranularity:
474        pos = nextLinePosition(pos, xPosForVerticalArrowNavigation(EXTENT));
475        break;
476    case ParagraphGranularity:
477        pos = nextParagraphPosition(pos, xPosForVerticalArrowNavigation(EXTENT));
478        break;
479    case SentenceBoundary:
480        pos = endOfSentence(endForPlatform());
481        break;
482    case LineBoundary:
483        pos = logicalEndOfLine(endForPlatform());
484        break;
485    case ParagraphBoundary:
486        pos = endOfParagraph(endForPlatform());
487        break;
488    case DocumentBoundary:
489        pos = endForPlatform();
490        if (isEditablePosition(pos.deepEquivalent()))
491            pos = endOfEditableContent(pos);
492        else
493            pos = endOfDocument(pos);
494        break;
495    case WebKitVisualWordGranularity:
496        break;
497    }
498
499    return pos;
500}
501
502VisiblePosition SelectionController::modifyMovingRight(TextGranularity granularity)
503{
504    VisiblePosition pos;
505    switch (granularity) {
506    case CharacterGranularity:
507        if (isRange()) {
508            if (directionOfEnclosingBlock() == LTR)
509                pos = VisiblePosition(m_selection.end(), m_selection.affinity());
510            else
511                pos = VisiblePosition(m_selection.start(), m_selection.affinity());
512        } else
513            pos = VisiblePosition(m_selection.extent(), m_selection.affinity()).right(true);
514        break;
515    case WordGranularity:
516    case SentenceGranularity:
517    case LineGranularity:
518    case ParagraphGranularity:
519    case SentenceBoundary:
520    case ParagraphBoundary:
521    case DocumentBoundary:
522        // FIXME: Implement all of the above.
523        pos = modifyMovingForward(granularity);
524        break;
525    case LineBoundary:
526        pos = rightBoundaryOfLine(startForPlatform(), directionOfEnclosingBlock());
527        break;
528    case WebKitVisualWordGranularity:
529        pos = rightWordPosition(VisiblePosition(m_selection.extent(), m_selection.affinity()));
530        break;
531    }
532    return pos;
533}
534
535VisiblePosition SelectionController::modifyMovingForward(TextGranularity granularity)
536{
537    VisiblePosition pos;
538    // FIXME: Stay in editable content for the less common granularities.
539    switch (granularity) {
540    case CharacterGranularity:
541        if (isRange())
542            pos = VisiblePosition(m_selection.end(), m_selection.affinity());
543        else
544            pos = VisiblePosition(m_selection.extent(), m_selection.affinity()).next(CannotCrossEditingBoundary);
545        break;
546    case WordGranularity:
547        pos = nextWordPosition(VisiblePosition(m_selection.extent(), m_selection.affinity()));
548        break;
549    case SentenceGranularity:
550        pos = nextSentencePosition(VisiblePosition(m_selection.extent(), m_selection.affinity()));
551        break;
552    case LineGranularity: {
553        // down-arrowing from a range selection that ends at the start of a line needs
554        // to leave the selection at that line start (no need to call nextLinePosition!)
555        pos = endForPlatform();
556        if (!isRange() || !isStartOfLine(pos))
557            pos = nextLinePosition(pos, xPosForVerticalArrowNavigation(START));
558        break;
559    }
560    case ParagraphGranularity:
561        pos = nextParagraphPosition(endForPlatform(), xPosForVerticalArrowNavigation(START));
562        break;
563    case SentenceBoundary:
564        pos = endOfSentence(endForPlatform());
565        break;
566    case LineBoundary:
567        pos = logicalEndOfLine(endForPlatform());
568        break;
569    case ParagraphBoundary:
570        pos = endOfParagraph(endForPlatform());
571        break;
572    case DocumentBoundary:
573        pos = endForPlatform();
574        if (isEditablePosition(pos.deepEquivalent()))
575            pos = endOfEditableContent(pos);
576        else
577            pos = endOfDocument(pos);
578        break;
579    case WebKitVisualWordGranularity:
580        break;
581    }
582    return pos;
583}
584
585VisiblePosition SelectionController::modifyExtendingLeft(TextGranularity granularity)
586{
587    VisiblePosition pos(m_selection.extent(), m_selection.affinity());
588
589    // The difference between modifyExtendingLeft and modifyExtendingBackward is:
590    // modifyExtendingBackward always extends backward logically.
591    // modifyExtendingLeft behaves the same as modifyExtendingBackward except for extending character or word,
592    // it extends backward logically if the enclosing block is LTR direction,
593    // but it extends forward logically if the enclosing block is RTL direction.
594    switch (granularity) {
595    case CharacterGranularity:
596        if (directionOfEnclosingBlock() == LTR)
597            pos = pos.previous(CannotCrossEditingBoundary);
598        else
599            pos = pos.next(CannotCrossEditingBoundary);
600        break;
601    case WordGranularity:
602        if (directionOfEnclosingBlock() == LTR)
603            pos = previousWordPosition(pos);
604        else
605            pos = nextWordPosition(pos);
606        break;
607    case LineBoundary:
608        if (directionOfEnclosingBlock() == LTR)
609            pos = modifyExtendingBackward(granularity);
610        else
611            pos = modifyExtendingForward(granularity);
612        break;
613    case SentenceGranularity:
614    case LineGranularity:
615    case ParagraphGranularity:
616    case SentenceBoundary:
617    case ParagraphBoundary:
618    case DocumentBoundary:
619        pos = modifyExtendingBackward(granularity);
620        break;
621    case WebKitVisualWordGranularity:
622        break;
623    }
624    return pos;
625}
626
627VisiblePosition SelectionController::modifyExtendingBackward(TextGranularity granularity)
628{
629    VisiblePosition pos(m_selection.extent(), m_selection.affinity());
630
631    // Extending a selection backward by word or character from just after a table selects
632    // the table.  This "makes sense" from the user perspective, esp. when deleting.
633    // It was done here instead of in VisiblePosition because we want VPs to iterate
634    // over everything.
635    switch (granularity) {
636    case CharacterGranularity:
637        pos = pos.previous(CannotCrossEditingBoundary);
638        break;
639    case WordGranularity:
640        pos = previousWordPosition(pos);
641        break;
642    case SentenceGranularity:
643        pos = previousSentencePosition(pos);
644        break;
645    case LineGranularity:
646        pos = previousLinePosition(pos, xPosForVerticalArrowNavigation(EXTENT));
647        break;
648    case ParagraphGranularity:
649        pos = previousParagraphPosition(pos, xPosForVerticalArrowNavigation(EXTENT));
650        break;
651    case SentenceBoundary:
652        pos = startOfSentence(startForPlatform());
653        break;
654    case LineBoundary:
655        pos = logicalStartOfLine(startForPlatform());
656        break;
657    case ParagraphBoundary:
658        pos = startOfParagraph(startForPlatform());
659        break;
660    case DocumentBoundary:
661        pos = startForPlatform();
662        if (isEditablePosition(pos.deepEquivalent()))
663            pos = startOfEditableContent(pos);
664        else
665            pos = startOfDocument(pos);
666        break;
667    case WebKitVisualWordGranularity:
668        break;
669    }
670    return pos;
671}
672
673VisiblePosition SelectionController::modifyMovingLeft(TextGranularity granularity)
674{
675    VisiblePosition pos;
676    switch (granularity) {
677    case CharacterGranularity:
678        if (isRange())
679            if (directionOfEnclosingBlock() == LTR)
680                pos = VisiblePosition(m_selection.start(), m_selection.affinity());
681            else
682                pos = VisiblePosition(m_selection.end(), m_selection.affinity());
683        else
684            pos = VisiblePosition(m_selection.extent(), m_selection.affinity()).left(true);
685        break;
686    case WordGranularity:
687    case SentenceGranularity:
688    case LineGranularity:
689    case ParagraphGranularity:
690    case SentenceBoundary:
691    case ParagraphBoundary:
692    case DocumentBoundary:
693        // FIXME: Implement all of the above.
694        pos = modifyMovingBackward(granularity);
695        break;
696    case LineBoundary:
697        pos = leftBoundaryOfLine(startForPlatform(), directionOfEnclosingBlock());
698        break;
699    case WebKitVisualWordGranularity:
700        pos = leftWordPosition(VisiblePosition(m_selection.extent(), m_selection.affinity()));
701        break;
702    }
703    return pos;
704}
705
706VisiblePosition SelectionController::modifyMovingBackward(TextGranularity granularity)
707{
708    VisiblePosition pos;
709    switch (granularity) {
710    case CharacterGranularity:
711        if (isRange())
712            pos = VisiblePosition(m_selection.start(), m_selection.affinity());
713        else
714            pos = VisiblePosition(m_selection.extent(), m_selection.affinity()).previous(CannotCrossEditingBoundary);
715        break;
716    case WordGranularity:
717        pos = previousWordPosition(VisiblePosition(m_selection.extent(), m_selection.affinity()));
718        break;
719    case SentenceGranularity:
720        pos = previousSentencePosition(VisiblePosition(m_selection.extent(), m_selection.affinity()));
721        break;
722    case LineGranularity:
723        pos = previousLinePosition(startForPlatform(), xPosForVerticalArrowNavigation(START));
724        break;
725    case ParagraphGranularity:
726        pos = previousParagraphPosition(startForPlatform(), xPosForVerticalArrowNavigation(START));
727        break;
728    case SentenceBoundary:
729        pos = startOfSentence(startForPlatform());
730        break;
731    case LineBoundary:
732        pos = logicalStartOfLine(startForPlatform());
733        break;
734    case ParagraphBoundary:
735        pos = startOfParagraph(startForPlatform());
736        break;
737    case DocumentBoundary:
738        pos = startForPlatform();
739        if (isEditablePosition(pos.deepEquivalent()))
740            pos = startOfEditableContent(pos);
741        else
742            pos = startOfDocument(pos);
743        break;
744    case WebKitVisualWordGranularity:
745        break;
746    }
747    return pos;
748}
749
750static bool isBoundary(TextGranularity granularity)
751{
752    return granularity == LineBoundary || granularity == ParagraphBoundary || granularity == DocumentBoundary;
753}
754
755bool SelectionController::modify(EAlteration alter, SelectionDirection direction, TextGranularity granularity, bool userTriggered)
756{
757    if (userTriggered) {
758        SelectionController trialSelectionController;
759        trialSelectionController.setSelection(m_selection);
760        trialSelectionController.setIsDirectional(m_isDirectional);
761        trialSelectionController.modify(alter, direction, granularity, false);
762
763        bool change = shouldChangeSelection(trialSelectionController.selection());
764        if (!change)
765            return false;
766    }
767
768    willBeModified(alter, direction);
769
770    bool wasRange = m_selection.isRange();
771    Position originalStartPosition = m_selection.start();
772    VisiblePosition position;
773    switch (direction) {
774    case DirectionRight:
775        if (alter == AlterationMove)
776            position = modifyMovingRight(granularity);
777        else
778            position = modifyExtendingRight(granularity);
779        break;
780    case DirectionForward:
781        if (alter == AlterationExtend)
782            position = modifyExtendingForward(granularity);
783        else
784            position = modifyMovingForward(granularity);
785        break;
786    case DirectionLeft:
787        if (alter == AlterationMove)
788            position = modifyMovingLeft(granularity);
789        else
790            position = modifyExtendingLeft(granularity);
791        break;
792    case DirectionBackward:
793        if (alter == AlterationExtend)
794            position = modifyExtendingBackward(granularity);
795        else
796            position = modifyMovingBackward(granularity);
797        break;
798    }
799
800    if (position.isNull())
801        return false;
802
803    if (isSpatialNavigationEnabled(m_frame))
804        if (!wasRange && alter == AlterationMove && position == originalStartPosition)
805            return false;
806
807    // Some of the above operations set an xPosForVerticalArrowNavigation.
808    // Setting a selection will clear it, so save it to possibly restore later.
809    // Note: the START position type is arbitrary because it is unused, it would be
810    // the requested position type if there were no xPosForVerticalArrowNavigation set.
811    int x = xPosForVerticalArrowNavigation(START);
812
813    switch (alter) {
814    case AlterationMove:
815        moveTo(position, userTriggered);
816        break;
817    case AlterationExtend:
818        // Standard Mac behavior when extending to a boundary is grow the selection rather than leaving the
819        // base in place and moving the extent. Matches NSTextView.
820        if (!m_frame || !m_frame->editor()->behavior().shouldAlwaysGrowSelectionWhenExtendingToBoundary() || m_selection.isCaret() || !isBoundary(granularity))
821            setExtent(position, userTriggered);
822        else {
823            TextDirection textDirection = directionOfEnclosingBlock();
824            if (direction == DirectionForward || (textDirection == LTR && direction == DirectionRight) || (textDirection == RTL && direction == DirectionLeft))
825                setEnd(position, userTriggered);
826            else
827                setStart(position, userTriggered);
828        }
829        break;
830    }
831
832    if (granularity == LineGranularity || granularity == ParagraphGranularity)
833        m_xPosForVerticalArrowNavigation = x;
834
835    if (userTriggered)
836        m_granularity = CharacterGranularity;
837
838
839    setCaretRectNeedsUpdate();
840
841    setIsDirectional(alter == AlterationExtend);
842
843    return true;
844}
845
846// FIXME: Maybe baseline would be better?
847static bool absoluteCaretY(const VisiblePosition &c, int &y)
848{
849    IntRect rect = c.absoluteCaretBounds();
850    if (rect.isEmpty())
851        return false;
852    y = rect.y() + rect.height() / 2;
853    return true;
854}
855
856bool SelectionController::modify(EAlteration alter, int verticalDistance, bool userTriggered, CursorAlignOnScroll align)
857{
858    if (!verticalDistance)
859        return false;
860
861    if (userTriggered) {
862        SelectionController trialSelectionController;
863        trialSelectionController.setSelection(m_selection);
864        trialSelectionController.setIsDirectional(m_isDirectional);
865        trialSelectionController.modify(alter, verticalDistance, false);
866
867        bool change = shouldChangeSelection(trialSelectionController.selection());
868        if (!change)
869            return false;
870    }
871
872    bool up = verticalDistance < 0;
873    if (up)
874        verticalDistance = -verticalDistance;
875
876    willBeModified(alter, up ? DirectionBackward : DirectionForward);
877
878    VisiblePosition pos;
879    int xPos = 0;
880    switch (alter) {
881    case AlterationMove:
882        pos = VisiblePosition(up ? m_selection.start() : m_selection.end(), m_selection.affinity());
883        xPos = xPosForVerticalArrowNavigation(up ? START : END);
884        m_selection.setAffinity(up ? UPSTREAM : DOWNSTREAM);
885        break;
886    case AlterationExtend:
887        pos = VisiblePosition(m_selection.extent(), m_selection.affinity());
888        xPos = xPosForVerticalArrowNavigation(EXTENT);
889        m_selection.setAffinity(DOWNSTREAM);
890        break;
891    }
892
893    int startY;
894    if (!absoluteCaretY(pos, startY))
895        return false;
896    if (up)
897        startY = -startY;
898    int lastY = startY;
899
900    VisiblePosition result;
901    VisiblePosition next;
902    for (VisiblePosition p = pos; ; p = next) {
903        next = (up ? previousLinePosition : nextLinePosition)(p, xPos);
904        if (next.isNull() || next == p)
905            break;
906        int nextY;
907        if (!absoluteCaretY(next, nextY))
908            break;
909        if (up)
910            nextY = -nextY;
911        if (nextY - startY > verticalDistance)
912            break;
913        if (nextY >= lastY) {
914            lastY = nextY;
915            result = next;
916        }
917    }
918
919    if (result.isNull())
920        return false;
921
922    switch (alter) {
923    case AlterationMove:
924        moveTo(result, userTriggered, align);
925        break;
926    case AlterationExtend:
927        setExtent(result, userTriggered);
928        break;
929    }
930
931    if (userTriggered)
932        m_granularity = CharacterGranularity;
933
934    setIsDirectional(alter == AlterationExtend);
935
936    return true;
937}
938
939int SelectionController::xPosForVerticalArrowNavigation(EPositionType type)
940{
941    int x = 0;
942
943    if (isNone())
944        return x;
945
946    Position pos;
947    switch (type) {
948    case START:
949        pos = m_selection.start();
950        break;
951    case END:
952        pos = m_selection.end();
953        break;
954    case BASE:
955        pos = m_selection.base();
956        break;
957    case EXTENT:
958        pos = m_selection.extent();
959        break;
960    }
961
962    Frame* frame = pos.anchorNode()->document()->frame();
963    if (!frame)
964        return x;
965
966    if (m_xPosForVerticalArrowNavigation == NoXPosForVerticalArrowNavigation) {
967        VisiblePosition visiblePosition(pos, m_selection.affinity());
968        // VisiblePosition creation can fail here if a node containing the selection becomes visibility:hidden
969        // after the selection is created and before this function is called.
970        x = visiblePosition.isNotNull() ? visiblePosition.xOffsetForVerticalNavigation() : 0;
971        m_xPosForVerticalArrowNavigation = x;
972    } else
973        x = m_xPosForVerticalArrowNavigation;
974
975    return x;
976}
977
978void SelectionController::clear()
979{
980    m_granularity = CharacterGranularity;
981    setSelection(VisibleSelection());
982}
983
984void SelectionController::setStart(const VisiblePosition &pos, bool userTriggered)
985{
986    if (m_selection.isBaseFirst())
987        setBase(pos, userTriggered);
988    else
989        setExtent(pos, userTriggered);
990}
991
992void SelectionController::setEnd(const VisiblePosition &pos, bool userTriggered)
993{
994    if (m_selection.isBaseFirst())
995        setExtent(pos, userTriggered);
996    else
997        setBase(pos, userTriggered);
998}
999
1000void SelectionController::setBase(const VisiblePosition &pos, bool userTriggered)
1001{
1002    SetSelectionOptions options = CloseTyping | ClearTypingStyle;
1003    if (userTriggered)
1004        options |= UserTriggered;
1005    setSelection(VisibleSelection(pos.deepEquivalent(), m_selection.extent(), pos.affinity()), options);
1006}
1007
1008void SelectionController::setExtent(const VisiblePosition &pos, bool userTriggered)
1009{
1010    SetSelectionOptions options = CloseTyping | ClearTypingStyle;
1011    if (userTriggered)
1012        options |= UserTriggered;
1013    setSelection(VisibleSelection(m_selection.base(), pos.deepEquivalent(), pos.affinity()), options);
1014}
1015
1016void SelectionController::setBase(const Position &pos, EAffinity affinity, bool userTriggered)
1017{
1018    SetSelectionOptions options = CloseTyping | ClearTypingStyle;
1019    if (userTriggered)
1020        options |= UserTriggered;
1021    setSelection(VisibleSelection(pos, m_selection.extent(), affinity), options);
1022}
1023
1024void SelectionController::setExtent(const Position &pos, EAffinity affinity, bool userTriggered)
1025{
1026    SetSelectionOptions options = CloseTyping | ClearTypingStyle;
1027    if (userTriggered)
1028        options |= UserTriggered;
1029    setSelection(VisibleSelection(m_selection.base(), pos, affinity), options);
1030}
1031
1032void SelectionController::setCaretRectNeedsUpdate(bool flag)
1033{
1034    m_caretRectNeedsUpdate = flag;
1035}
1036
1037void SelectionController::updateCaretRect()
1038{
1039    if (isNone() || !m_selection.start().anchorNode()->inDocument() || !m_selection.end().anchorNode()->inDocument()) {
1040        m_caretRect = IntRect();
1041        return;
1042    }
1043
1044    m_selection.start().anchorNode()->document()->updateStyleIfNeeded();
1045
1046    m_caretRect = IntRect();
1047
1048    if (isCaret()) {
1049        VisiblePosition pos(m_selection.start(), m_selection.affinity());
1050        if (pos.isNotNull()) {
1051            ASSERT(pos.deepEquivalent().deprecatedNode()->renderer());
1052
1053            // First compute a rect local to the renderer at the selection start
1054            RenderObject* renderer;
1055            IntRect localRect = pos.localCaretRect(renderer);
1056
1057            // Get the renderer that will be responsible for painting the caret (which
1058            // is either the renderer we just found, or one of its containers)
1059            RenderObject* caretPainter = caretRenderer();
1060
1061            // Compute an offset between the renderer and the caretPainter
1062            bool unrooted = false;
1063            while (renderer != caretPainter) {
1064                RenderObject* containerObject = renderer->container();
1065                if (!containerObject) {
1066                    unrooted = true;
1067                    break;
1068                }
1069                localRect.move(renderer->offsetFromContainer(containerObject, localRect.location()));
1070                renderer = containerObject;
1071            }
1072
1073            if (!unrooted)
1074                m_caretRect = localRect;
1075
1076            m_absCaretBoundsDirty = true;
1077        }
1078    }
1079
1080    m_caretRectNeedsUpdate = false;
1081}
1082
1083RenderObject* SelectionController::caretRenderer() const
1084{
1085    Node* node = m_selection.start().deprecatedNode();
1086    if (!node)
1087        return 0;
1088
1089    RenderObject* renderer = node->renderer();
1090    if (!renderer)
1091        return 0;
1092
1093    // if caretNode is a block and caret is inside it then caret should be painted by that block
1094    bool paintedByBlock = renderer->isBlockFlow() && caretRendersInsideNode(node);
1095    return paintedByBlock ? renderer : renderer->containingBlock();
1096}
1097
1098IntRect SelectionController::localCaretRect()
1099{
1100    if (m_caretRectNeedsUpdate)
1101        updateCaretRect();
1102
1103    return m_caretRect;
1104}
1105
1106IntRect SelectionController::absoluteBoundsForLocalRect(const IntRect& rect) const
1107{
1108    RenderObject* caretPainter = caretRenderer();
1109    if (!caretPainter)
1110        return IntRect();
1111
1112    IntRect localRect(rect);
1113    if (caretPainter->isBox())
1114        toRenderBox(caretPainter)->flipForWritingMode(localRect);
1115    return caretPainter->localToAbsoluteQuad(FloatRect(localRect)).enclosingBoundingBox();
1116}
1117
1118IntRect SelectionController::absoluteCaretBounds()
1119{
1120    recomputeCaretRect();
1121    return m_absCaretBounds;
1122}
1123
1124static IntRect repaintRectForCaret(IntRect caret)
1125{
1126    if (caret.isEmpty())
1127        return IntRect();
1128    // Ensure that the dirty rect intersects the block that paints the caret even in the case where
1129    // the caret itself is just outside the block. See <https://bugs.webkit.org/show_bug.cgi?id=19086>.
1130    caret.inflateX(1);
1131    return caret;
1132}
1133
1134IntRect SelectionController::caretRepaintRect() const
1135{
1136    return absoluteBoundsForLocalRect(repaintRectForCaret(localCaretRectForPainting()));
1137}
1138
1139bool SelectionController::recomputeCaretRect()
1140{
1141    if (!m_caretRectNeedsUpdate)
1142        return false;
1143
1144    if (!m_frame)
1145        return false;
1146
1147    FrameView* v = m_frame->document()->view();
1148    if (!v)
1149        return false;
1150
1151    IntRect oldRect = m_caretRect;
1152    IntRect newRect = localCaretRect();
1153    if (oldRect == newRect && !m_absCaretBoundsDirty)
1154        return false;
1155
1156    IntRect oldAbsCaretBounds = m_absCaretBounds;
1157    // FIXME: Rename m_caretRect to m_localCaretRect.
1158    m_absCaretBounds = absoluteBoundsForLocalRect(m_caretRect);
1159    m_absCaretBoundsDirty = false;
1160
1161    if (oldAbsCaretBounds == m_absCaretBounds)
1162        return false;
1163
1164    IntRect oldAbsoluteCaretRepaintBounds = m_absoluteCaretRepaintBounds;
1165    // We believe that we need to inflate the local rect before transforming it to obtain the repaint bounds.
1166    m_absoluteCaretRepaintBounds = caretRepaintRect();
1167
1168#if ENABLE(TEXT_CARET)
1169    if (RenderView* view = toRenderView(m_frame->document()->renderer())) {
1170        // FIXME: make caret repainting container-aware.
1171        view->repaintRectangleInViewAndCompositedLayers(oldAbsoluteCaretRepaintBounds, false);
1172        if (shouldRepaintCaret(view))
1173            view->repaintRectangleInViewAndCompositedLayers(m_absoluteCaretRepaintBounds, false);
1174    }
1175#endif
1176    return true;
1177}
1178
1179bool SelectionController::shouldRepaintCaret(const RenderView* view) const
1180{
1181    ASSERT(view);
1182    Frame* frame = view->frameView() ? view->frameView()->frame() : 0; // The frame where the selection started.
1183    bool caretBrowsing = frame && frame->settings() && frame->settings()->caretBrowsingEnabled();
1184    return (caretBrowsing || isContentEditable());
1185}
1186
1187void SelectionController::invalidateCaretRect()
1188{
1189    if (!isCaret())
1190        return;
1191
1192    Document* d = m_selection.start().anchorNode()->document();
1193
1194    // recomputeCaretRect will always return false for the drag caret,
1195    // because its m_frame is always 0.
1196    bool caretRectChanged = recomputeCaretRect();
1197
1198    // EDIT FIXME: This is an unfortunate hack.
1199    // Basically, we can't trust this layout position since we
1200    // can't guarantee that the check to see if we are in unrendered
1201    // content will work at this point. We may have to wait for
1202    // a layout and re-render of the document to happen. So, resetting this
1203    // flag will cause another caret layout to happen the first time
1204    // that we try to paint the caret after this call. That one will work since
1205    // it happens after the document has accounted for any editing
1206    // changes which may have been done.
1207    // And, we need to leave this layout here so the caret moves right
1208    // away after clicking.
1209    m_caretRectNeedsUpdate = true;
1210
1211    if (!caretRectChanged) {
1212        RenderView* view = toRenderView(d->renderer());
1213        if (view && shouldRepaintCaret(view))
1214            view->repaintRectangleInViewAndCompositedLayers(caretRepaintRect(), false);
1215    }
1216}
1217
1218void SelectionController::paintCaret(GraphicsContext* context, int tx, int ty, const IntRect& clipRect)
1219{
1220#if ENABLE(TEXT_CARET)
1221    if (!m_caretVisible)
1222        return;
1223    if (!m_caretPaint)
1224        return;
1225    if (!m_selection.isCaret())
1226        return;
1227
1228    IntRect drawingRect = localCaretRectForPainting();
1229    if (caretRenderer() && caretRenderer()->isBox())
1230        toRenderBox(caretRenderer())->flipForWritingMode(drawingRect);
1231    drawingRect.move(tx, ty);
1232    IntRect caret = intersection(drawingRect, clipRect);
1233    if (caret.isEmpty())
1234        return;
1235
1236    Color caretColor = Color::black;
1237    ColorSpace colorSpace = ColorSpaceDeviceRGB;
1238    Element* element = rootEditableElement();
1239    if (element && element->renderer()) {
1240        caretColor = element->renderer()->style()->visitedDependentColor(CSSPropertyColor);
1241        colorSpace = element->renderer()->style()->colorSpace();
1242    }
1243
1244    context->fillRect(caret, caretColor, colorSpace);
1245#else
1246    UNUSED_PARAM(context);
1247    UNUSED_PARAM(tx);
1248    UNUSED_PARAM(ty);
1249    UNUSED_PARAM(clipRect);
1250#endif
1251}
1252
1253void SelectionController::debugRenderer(RenderObject *r, bool selected) const
1254{
1255    if (r->node()->isElementNode()) {
1256        Element* element = static_cast<Element *>(r->node());
1257        fprintf(stderr, "%s%s\n", selected ? "==> " : "    ", element->localName().string().utf8().data());
1258    } else if (r->isText()) {
1259        RenderText* textRenderer = toRenderText(r);
1260        if (!textRenderer->textLength() || !textRenderer->firstTextBox()) {
1261            fprintf(stderr, "%s#text (empty)\n", selected ? "==> " : "    ");
1262            return;
1263        }
1264
1265        static const int max = 36;
1266        String text = textRenderer->text();
1267        int textLength = text.length();
1268        if (selected) {
1269            int offset = 0;
1270            if (r->node() == m_selection.start().containerNode())
1271                offset = m_selection.start().computeOffsetInContainerNode();
1272            else if (r->node() == m_selection.end().containerNode())
1273                offset = m_selection.end().computeOffsetInContainerNode();
1274
1275            int pos;
1276            InlineTextBox* box = textRenderer->findNextInlineTextBox(offset, pos);
1277            text = text.substring(box->start(), box->len());
1278
1279            String show;
1280            int mid = max / 2;
1281            int caret = 0;
1282
1283            // text is shorter than max
1284            if (textLength < max) {
1285                show = text;
1286                caret = pos;
1287            } else if (pos - mid < 0) {
1288                // too few characters to left
1289                show = text.left(max - 3) + "...";
1290                caret = pos;
1291            } else if (pos - mid >= 0 && pos + mid <= textLength) {
1292                // enough characters on each side
1293                show = "..." + text.substring(pos - mid + 3, max - 6) + "...";
1294                caret = mid;
1295            } else {
1296                // too few characters on right
1297                show = "..." + text.right(max - 3);
1298                caret = pos - (textLength - show.length());
1299            }
1300
1301            show.replace('\n', ' ');
1302            show.replace('\r', ' ');
1303            fprintf(stderr, "==> #text : \"%s\" at offset %d\n", show.utf8().data(), pos);
1304            fprintf(stderr, "           ");
1305            for (int i = 0; i < caret; i++)
1306                fprintf(stderr, " ");
1307            fprintf(stderr, "^\n");
1308        } else {
1309            if ((int)text.length() > max)
1310                text = text.left(max - 3) + "...";
1311            else
1312                text = text.left(max);
1313            fprintf(stderr, "    #text : \"%s\"\n", text.utf8().data());
1314        }
1315    }
1316}
1317
1318bool SelectionController::contains(const IntPoint& point)
1319{
1320    Document* document = m_frame->document();
1321
1322    // Treat a collapsed selection like no selection.
1323    if (!isRange())
1324        return false;
1325    if (!document->renderer())
1326        return false;
1327
1328    HitTestRequest request(HitTestRequest::ReadOnly |
1329                           HitTestRequest::Active);
1330    HitTestResult result(point);
1331    document->renderView()->layer()->hitTest(request, result);
1332    Node* innerNode = result.innerNode();
1333    if (!innerNode || !innerNode->renderer())
1334        return false;
1335
1336    VisiblePosition visiblePos(innerNode->renderer()->positionForPoint(result.localPoint()));
1337    if (visiblePos.isNull())
1338        return false;
1339
1340    if (m_selection.visibleStart().isNull() || m_selection.visibleEnd().isNull())
1341        return false;
1342
1343    Position start(m_selection.visibleStart().deepEquivalent());
1344    Position end(m_selection.visibleEnd().deepEquivalent());
1345    Position p(visiblePos.deepEquivalent());
1346
1347    return comparePositions(start, p) <= 0 && comparePositions(p, end) <= 0;
1348}
1349
1350// Workaround for the fact that it's hard to delete a frame.
1351// Call this after doing user-triggered selections to make it easy to delete the frame you entirely selected.
1352// Can't do this implicitly as part of every setSelection call because in some contexts it might not be good
1353// for the focus to move to another frame. So instead we call it from places where we are selecting with the
1354// mouse or the keyboard after setting the selection.
1355void SelectionController::selectFrameElementInParentIfFullySelected()
1356{
1357    // Find the parent frame; if there is none, then we have nothing to do.
1358    Frame* parent = m_frame->tree()->parent();
1359    if (!parent)
1360        return;
1361    Page* page = m_frame->page();
1362    if (!page)
1363        return;
1364
1365    // Check if the selection contains the entire frame contents; if not, then there is nothing to do.
1366    if (!isRange())
1367        return;
1368    if (!isStartOfDocument(selection().visibleStart()))
1369        return;
1370    if (!isEndOfDocument(selection().visibleEnd()))
1371        return;
1372
1373    // Get to the <iframe> or <frame> (or even <object>) element in the parent frame.
1374    Element* ownerElement = m_frame->ownerElement();
1375    if (!ownerElement)
1376        return;
1377    ContainerNode* ownerElementParent = ownerElement->parentNode();
1378    if (!ownerElementParent)
1379        return;
1380
1381    // This method's purpose is it to make it easier to select iframes (in order to delete them).  Don't do anything if the iframe isn't deletable.
1382    if (!ownerElementParent->rendererIsEditable())
1383        return;
1384
1385    // Create compute positions before and after the element.
1386    unsigned ownerElementNodeIndex = ownerElement->nodeIndex();
1387    VisiblePosition beforeOwnerElement(VisiblePosition(Position(ownerElementParent, ownerElementNodeIndex, Position::PositionIsOffsetInAnchor)));
1388    VisiblePosition afterOwnerElement(VisiblePosition(Position(ownerElementParent, ownerElementNodeIndex + 1, Position::PositionIsOffsetInAnchor), VP_UPSTREAM_IF_POSSIBLE));
1389
1390    // Focus on the parent frame, and then select from before this element to after.
1391    VisibleSelection newSelection(beforeOwnerElement, afterOwnerElement);
1392    if (parent->selection()->shouldChangeSelection(newSelection)) {
1393        page->focusController()->setFocusedFrame(parent);
1394        parent->selection()->setSelection(newSelection);
1395    }
1396}
1397
1398void SelectionController::selectAll()
1399{
1400    Document* document = m_frame->document();
1401
1402    if (document->focusedNode() && document->focusedNode()->canSelectAll()) {
1403        document->focusedNode()->selectAll();
1404        return;
1405    }
1406
1407    Node* root = 0;
1408    if (isContentEditable())
1409        root = highestEditableRoot(m_selection.start());
1410    else {
1411        root = shadowTreeRootNode();
1412        if (!root)
1413            root = document->documentElement();
1414    }
1415    if (!root)
1416        return;
1417    VisibleSelection newSelection(VisibleSelection::selectionFromContentsOfNode(root));
1418    if (shouldChangeSelection(newSelection))
1419        setSelection(newSelection);
1420    selectFrameElementInParentIfFullySelected();
1421    notifyRendererOfSelectionChange(true);
1422}
1423
1424bool SelectionController::setSelectedRange(Range* range, EAffinity affinity, bool closeTyping)
1425{
1426    if (!range)
1427        return false;
1428
1429    ExceptionCode ec = 0;
1430    Node* startContainer = range->startContainer(ec);
1431    if (ec)
1432        return false;
1433
1434    Node* endContainer = range->endContainer(ec);
1435    if (ec)
1436        return false;
1437
1438    ASSERT(startContainer);
1439    ASSERT(endContainer);
1440    ASSERT(startContainer->document() == endContainer->document());
1441
1442    m_frame->document()->updateLayoutIgnorePendingStylesheets();
1443
1444    // Non-collapsed ranges are not allowed to start at the end of a line that is wrapped,
1445    // they start at the beginning of the next line instead
1446    bool collapsed = range->collapsed(ec);
1447    if (ec)
1448        return false;
1449
1450    int startOffset = range->startOffset(ec);
1451    if (ec)
1452        return false;
1453
1454    int endOffset = range->endOffset(ec);
1455    if (ec)
1456        return false;
1457
1458    // FIXME: Can we provide extentAffinity?
1459    VisiblePosition visibleStart(Position(startContainer, startOffset, Position::PositionIsOffsetInAnchor), collapsed ? affinity : DOWNSTREAM);
1460    VisiblePosition visibleEnd(Position(endContainer, endOffset, Position::PositionIsOffsetInAnchor), SEL_DEFAULT_AFFINITY);
1461    SetSelectionOptions options = ClearTypingStyle;
1462    if (closeTyping)
1463        options |= CloseTyping;
1464    setSelection(VisibleSelection(visibleStart, visibleEnd), options);
1465    return true;
1466}
1467
1468bool SelectionController::isInPasswordField() const
1469{
1470    ASSERT(start().isNull() || start().anchorType() == Position::PositionIsOffsetInAnchor
1471           || start().containerNode() || !start().anchorNode()->shadowAncestorNode());
1472    Node* startNode = start().containerNode();
1473    if (!startNode)
1474        return false;
1475
1476    startNode = startNode->shadowAncestorNode();
1477    if (!startNode)
1478        return false;
1479
1480    if (!startNode->hasTagName(inputTag))
1481        return false;
1482
1483    return static_cast<HTMLInputElement*>(startNode)->isPasswordField();
1484}
1485
1486bool SelectionController::caretRendersInsideNode(Node* node) const
1487{
1488    if (!node)
1489        return false;
1490    return !isTableElement(node) && !editingIgnoresContent(node);
1491}
1492
1493void SelectionController::focusedOrActiveStateChanged()
1494{
1495    bool activeAndFocused = isFocusedAndActive();
1496
1497    // Because RenderObject::selectionBackgroundColor() and
1498    // RenderObject::selectionForegroundColor() check if the frame is active,
1499    // we have to update places those colors were painted.
1500    if (RenderView* view = toRenderView(m_frame->document()->renderer()))
1501        view->repaintRectangleInViewAndCompositedLayers(enclosingIntRect(bounds()));
1502
1503    // Caret appears in the active frame.
1504    if (activeAndFocused)
1505        setSelectionFromNone();
1506    setCaretVisible(activeAndFocused);
1507
1508    // Update for caps lock state
1509    m_frame->eventHandler()->capsLockStateMayHaveChanged();
1510
1511    // Because CSSStyleSelector::checkOneSelector() and
1512    // RenderTheme::isFocused() check if the frame is active, we have to
1513    // update style and theme state that depended on those.
1514    if (Node* node = m_frame->document()->focusedNode()) {
1515        node->setNeedsStyleRecalc();
1516        if (RenderObject* renderer = node->renderer())
1517            if (renderer && renderer->style()->hasAppearance())
1518                renderer->theme()->stateChanged(renderer, FocusState);
1519    }
1520
1521    // Secure keyboard entry is set by the active frame.
1522    if (m_frame->document()->useSecureKeyboardEntryWhenActive())
1523        setUseSecureKeyboardEntry(activeAndFocused);
1524}
1525
1526void SelectionController::pageActivationChanged()
1527{
1528    focusedOrActiveStateChanged();
1529}
1530
1531void SelectionController::updateSecureKeyboardEntryIfActive()
1532{
1533    if (m_frame->document() && isFocusedAndActive())
1534        setUseSecureKeyboardEntry(m_frame->document()->useSecureKeyboardEntryWhenActive());
1535}
1536
1537void SelectionController::setUseSecureKeyboardEntry(bool enable)
1538{
1539    if (enable)
1540        enableSecureTextInput();
1541    else
1542        disableSecureTextInput();
1543}
1544
1545void SelectionController::setFocused(bool flag)
1546{
1547    if (m_focused == flag)
1548        return;
1549    m_focused = flag;
1550
1551    focusedOrActiveStateChanged();
1552}
1553
1554bool SelectionController::isFocusedAndActive() const
1555{
1556    return m_focused && m_frame->page() && m_frame->page()->focusController()->isActive();
1557}
1558
1559void SelectionController::updateAppearance()
1560{
1561    ASSERT(!m_isDragCaretController);
1562
1563#if ENABLE(TEXT_CARET)
1564    bool caretRectChanged = recomputeCaretRect();
1565
1566    bool caretBrowsing = m_frame->settings() && m_frame->settings()->caretBrowsingEnabled();
1567    bool shouldBlink = m_caretVisible
1568        && isCaret() && (isContentEditable() || caretBrowsing);
1569
1570    // If the caret moved, stop the blink timer so we can restart with a
1571    // black caret in the new location.
1572    if (caretRectChanged || !shouldBlink)
1573        m_caretBlinkTimer.stop();
1574
1575    // Start blinking with a black caret. Be sure not to restart if we're
1576    // already blinking in the right location.
1577    if (shouldBlink && !m_caretBlinkTimer.isActive()) {
1578        if (double blinkInterval = m_frame->page()->theme()->caretBlinkInterval())
1579            m_caretBlinkTimer.startRepeating(blinkInterval);
1580
1581        if (!m_caretPaint) {
1582            m_caretPaint = true;
1583            invalidateCaretRect();
1584        }
1585    }
1586#endif
1587
1588    // We need to update style in case the node containing the selection is made display:none.
1589    m_frame->document()->updateStyleIfNeeded();
1590
1591#if PLATFORM(ANDROID)
1592    return;
1593#endif
1594
1595    RenderView* view = m_frame->contentRenderer();
1596    if (!view)
1597        return;
1598
1599    VisibleSelection selection = this->selection();
1600
1601    if (!selection.isRange()) {
1602        view->clearSelection();
1603        return;
1604    }
1605
1606    // Use the rightmost candidate for the start of the selection, and the leftmost candidate for the end of the selection.
1607    // Example: foo <a>bar</a>.  Imagine that a line wrap occurs after 'foo', and that 'bar' is selected.   If we pass [foo, 3]
1608    // as the start of the selection, the selection painting code will think that content on the line containing 'foo' is selected
1609    // and will fill the gap before 'bar'.
1610    Position startPos = selection.start();
1611    Position candidate = startPos.downstream();
1612    if (candidate.isCandidate())
1613        startPos = candidate;
1614    Position endPos = selection.end();
1615    candidate = endPos.upstream();
1616    if (candidate.isCandidate())
1617        endPos = candidate;
1618
1619    // We can get into a state where the selection endpoints map to the same VisiblePosition when a selection is deleted
1620    // because we don't yet notify the SelectionController of text removal.
1621    if (startPos.isNotNull() && endPos.isNotNull() && selection.visibleStart() != selection.visibleEnd()) {
1622        RenderObject* startRenderer = startPos.deprecatedNode()->renderer();
1623        RenderObject* endRenderer = endPos.deprecatedNode()->renderer();
1624        view->setSelection(startRenderer, startPos.deprecatedEditingOffset(), endRenderer, endPos.deprecatedEditingOffset());
1625    }
1626}
1627
1628void SelectionController::setCaretVisible(bool flag)
1629{
1630    if (m_caretVisible == flag)
1631        return;
1632    clearCaretRectIfNeeded();
1633    m_caretVisible = flag;
1634    updateAppearance();
1635}
1636
1637void SelectionController::clearCaretRectIfNeeded()
1638{
1639#if ENABLE(TEXT_CARET)
1640    if (!m_caretPaint)
1641        return;
1642    m_caretPaint = false;
1643    invalidateCaretRect();
1644#endif
1645}
1646
1647void SelectionController::caretBlinkTimerFired(Timer<SelectionController>*)
1648{
1649#if ENABLE(TEXT_CARET)
1650    ASSERT(m_caretVisible);
1651    ASSERT(isCaret());
1652    bool caretPaint = m_caretPaint;
1653    if (isCaretBlinkingSuspended() && caretPaint)
1654        return;
1655    m_caretPaint = !caretPaint;
1656    invalidateCaretRect();
1657#endif
1658}
1659
1660void SelectionController::notifyRendererOfSelectionChange(bool userTriggered)
1661{
1662    m_frame->document()->updateStyleIfNeeded();
1663
1664    if (!rootEditableElement())
1665        return;
1666
1667    RenderObject* renderer = rootEditableElement()->shadowAncestorNode()->renderer();
1668    if (!renderer || !renderer->isTextControl())
1669        return;
1670
1671    toRenderTextControl(renderer)->selectionChanged(userTriggered);
1672}
1673
1674// Helper function that tells whether a particular node is an element that has an entire
1675// Frame and FrameView, a <frame>, <iframe>, or <object>.
1676static bool isFrameElement(const Node* n)
1677{
1678    if (!n)
1679        return false;
1680    RenderObject* renderer = n->renderer();
1681    if (!renderer || !renderer->isWidget())
1682        return false;
1683    Widget* widget = toRenderWidget(renderer)->widget();
1684    return widget && widget->isFrameView();
1685}
1686
1687void SelectionController::setFocusedNodeIfNeeded()
1688{
1689    if (isNone() || !isFocused())
1690        return;
1691
1692    bool caretBrowsing = m_frame->settings() && m_frame->settings()->caretBrowsingEnabled();
1693    if (caretBrowsing) {
1694        if (Node* anchor = enclosingAnchorElement(base())) {
1695            m_frame->page()->focusController()->setFocusedNode(anchor, m_frame);
1696            return;
1697        }
1698    }
1699
1700    if (Node* target = rootEditableElement()) {
1701        // Walk up the DOM tree to search for a node to focus.
1702        while (target) {
1703            // We don't want to set focus on a subframe when selecting in a parent frame,
1704            // so add the !isFrameElement check here. There's probably a better way to make this
1705            // work in the long term, but this is the safest fix at this time.
1706            if (target && target->isMouseFocusable() && !isFrameElement(target)) {
1707                m_frame->page()->focusController()->setFocusedNode(target, m_frame);
1708                return;
1709            }
1710            target = target->parentOrHostNode();
1711        }
1712        m_frame->document()->setFocusedNode(0);
1713    }
1714
1715    if (caretBrowsing)
1716        m_frame->page()->focusController()->setFocusedNode(0, m_frame);
1717}
1718
1719void SelectionController::paintDragCaret(GraphicsContext* p, int tx, int ty, const IntRect& clipRect) const
1720{
1721#if ENABLE(TEXT_CARET)
1722    SelectionController* dragCaretController = m_frame->page()->dragCaretController();
1723    ASSERT(dragCaretController->selection().isCaret());
1724    if (dragCaretController->selection().start().anchorNode()->document()->frame() == m_frame)
1725        dragCaretController->paintCaret(p, tx, ty, clipRect);
1726#else
1727    UNUSED_PARAM(p);
1728    UNUSED_PARAM(tx);
1729    UNUSED_PARAM(ty);
1730    UNUSED_PARAM(clipRect);
1731#endif
1732}
1733
1734PassRefPtr<CSSMutableStyleDeclaration> SelectionController::copyTypingStyle() const
1735{
1736    if (!m_typingStyle || !m_typingStyle->style())
1737        return 0;
1738    return m_typingStyle->style()->copy();
1739}
1740
1741bool SelectionController::shouldDeleteSelection(const VisibleSelection& selection) const
1742{
1743    return m_frame->editor()->client()->shouldDeleteRange(selection.toNormalizedRange().get());
1744}
1745
1746FloatRect SelectionController::bounds(bool clipToVisibleContent) const
1747{
1748    RenderView* root = m_frame->contentRenderer();
1749    FrameView* view = m_frame->view();
1750    if (!root || !view)
1751        return IntRect();
1752
1753    IntRect selectionRect = root->selectionBounds(clipToVisibleContent);
1754    return clipToVisibleContent ? intersection(selectionRect, view->visibleContentRect()) : selectionRect;
1755}
1756
1757void SelectionController::getClippedVisibleTextRectangles(Vector<FloatRect>& rectangles) const
1758{
1759    RenderView* root = m_frame->contentRenderer();
1760    if (!root)
1761        return;
1762
1763    FloatRect visibleContentRect = m_frame->view()->visibleContentRect();
1764
1765    Vector<FloatQuad> quads;
1766    toNormalizedRange()->textQuads(quads, true);
1767
1768    // FIXME: We are appending empty rectangles to the list for those that fall outside visibleContentRect.
1769    // It might be better to omit those rectangles entirely.
1770    size_t size = quads.size();
1771    for (size_t i = 0; i < size; ++i)
1772        rectangles.append(intersection(quads[i].enclosingBoundingBox(), visibleContentRect));
1773}
1774
1775// Scans logically forward from "start", including any child frames.
1776static HTMLFormElement* scanForForm(Node* start)
1777{
1778    for (Node* node = start; node; node = node->traverseNextNode()) {
1779        if (node->hasTagName(formTag))
1780            return static_cast<HTMLFormElement*>(node);
1781        if (node->isHTMLElement() && toHTMLElement(node)->isFormControlElement())
1782            return static_cast<HTMLFormControlElement*>(node)->form();
1783        if (node->hasTagName(frameTag) || node->hasTagName(iframeTag)) {
1784            Node* childDocument = static_cast<HTMLFrameElementBase*>(node)->contentDocument();
1785            if (HTMLFormElement* frameResult = scanForForm(childDocument))
1786                return frameResult;
1787        }
1788    }
1789    return 0;
1790}
1791
1792// We look for either the form containing the current focus, or for one immediately after it
1793HTMLFormElement* SelectionController::currentForm() const
1794{
1795    // Start looking either at the active (first responder) node, or where the selection is.
1796    Node* start = m_frame->document()->focusedNode();
1797    if (!start)
1798        start = this->start().deprecatedNode();
1799
1800    // Try walking up the node tree to find a form element.
1801    Node* node;
1802    for (node = start; node; node = node->parentNode()) {
1803        if (node->hasTagName(formTag))
1804            return static_cast<HTMLFormElement*>(node);
1805        if (node->isHTMLElement() && toHTMLElement(node)->isFormControlElement())
1806            return static_cast<HTMLFormControlElement*>(node)->form();
1807    }
1808
1809    // Try walking forward in the node tree to find a form element.
1810    return scanForForm(start);
1811}
1812
1813void SelectionController::revealSelection(const ScrollAlignment& alignment, bool revealExtent)
1814{
1815    IntRect rect;
1816
1817    switch (selectionType()) {
1818    case VisibleSelection::NoSelection:
1819        return;
1820    case VisibleSelection::CaretSelection:
1821        rect = absoluteCaretBounds();
1822        break;
1823    case VisibleSelection::RangeSelection:
1824        rect = revealExtent ? VisiblePosition(extent()).absoluteCaretBounds() : enclosingIntRect(bounds(false));
1825        break;
1826    }
1827
1828    Position start = this->start();
1829    ASSERT(start.deprecatedNode());
1830    if (start.deprecatedNode() && start.deprecatedNode()->renderer()) {
1831        // FIXME: This code only handles scrolling the startContainer's layer, but
1832        // the selection rect could intersect more than just that.
1833        // See <rdar://problem/4799899>.
1834        if (RenderLayer* layer = start.deprecatedNode()->renderer()->enclosingLayer()) {
1835            layer->scrollRectToVisible(rect, false, alignment, alignment);
1836            updateAppearance();
1837        }
1838    }
1839}
1840
1841void SelectionController::setSelectionFromNone()
1842{
1843    // Put a caret inside the body if the entire frame is editable (either the
1844    // entire WebView is editable or designMode is on for this document).
1845
1846    Document* document = m_frame->document();
1847    bool caretBrowsing = m_frame->settings() && m_frame->settings()->caretBrowsingEnabled();
1848    if (!isNone() || !(document->rendererIsEditable() || caretBrowsing))
1849        return;
1850
1851    Node* node = document->documentElement();
1852    while (node && !node->hasTagName(bodyTag))
1853        node = node->traverseNextNode();
1854    if (node)
1855        setSelection(VisibleSelection(firstPositionInOrBeforeNode(node), DOWNSTREAM));
1856}
1857
1858bool SelectionController::shouldChangeSelection(const VisibleSelection& newSelection) const
1859{
1860    return m_frame->editor()->shouldChangeSelection(selection(), newSelection, newSelection.affinity(), false);
1861}
1862
1863#ifndef NDEBUG
1864
1865void SelectionController::formatForDebugger(char* buffer, unsigned length) const
1866{
1867    m_selection.formatForDebugger(buffer, length);
1868}
1869
1870void SelectionController::showTreeForThis() const
1871{
1872    m_selection.showTreeForThis();
1873}
1874
1875#endif
1876
1877}
1878
1879#ifndef NDEBUG
1880
1881void showTree(const WebCore::SelectionController& sel)
1882{
1883    sel.showTreeForThis();
1884}
1885
1886void showTree(const WebCore::SelectionController* sel)
1887{
1888    if (sel)
1889        sel->showTreeForThis();
1890}
1891
1892#endif
1893