771d67fc7937da8710f6a3d7e3c32ba20116d14e
[WebKit-https.git] / WebCore / editing / Selection.cpp
1 /*
2  * Copyright (C) 2004, 2005, 2006 Apple Computer, 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 "Selection.h"
28
29 #include "Document.h"
30 #include "Element.h"
31 #include "htmlediting.h"
32 #include "VisiblePosition.h"
33 #include "visible_units.h"
34 #include "Range.h"
35 #include <wtf/Assertions.h>
36
37 namespace WebCore {
38
39 Selection::Selection()
40     : m_affinity(DOWNSTREAM)
41     , m_granularity(CharacterGranularity)
42     , m_state(NONE)
43     , m_baseIsFirst(true)
44 {
45 }
46
47 Selection::Selection(const Position& pos, EAffinity affinity)
48     : m_base(pos)
49     , m_extent(pos)
50     , m_affinity(affinity)
51     , m_granularity(CharacterGranularity)
52 {
53     validate();
54 }
55
56 Selection::Selection(const Position& base, const Position& extent, EAffinity affinity)
57     : m_base(base)
58     , m_extent(extent)
59     , m_affinity(affinity)
60     , m_granularity(CharacterGranularity)
61 {
62     validate();
63 }
64
65 Selection::Selection(const VisiblePosition& pos)
66     : m_base(pos.deepEquivalent())
67     , m_extent(pos.deepEquivalent())
68     , m_affinity(pos.affinity())
69     , m_granularity(CharacterGranularity)
70 {
71     validate();
72 }
73
74 Selection::Selection(const VisiblePosition& base, const VisiblePosition& extent)
75     : m_base(base.deepEquivalent())
76     , m_extent(extent.deepEquivalent())
77     , m_affinity(base.affinity())
78     , m_granularity(CharacterGranularity)
79 {
80     validate();
81 }
82
83 Selection::Selection(const Range* range, EAffinity affinity)
84     : m_base(range->startPosition())
85     , m_extent(range->endPosition())
86     , m_affinity(affinity)
87     , m_granularity(CharacterGranularity)
88 {
89     validate();
90 }
91
92 Selection Selection::selectionFromContentsOfNode(Node* node)
93 {
94     return Selection(Position(node, 0), Position(node, maxDeepOffset(node)), DOWNSTREAM);
95 }
96
97 void Selection::setBase(const Position& position)
98 {
99     m_base = position;
100     validate();
101 }
102
103 void Selection::setBase(const VisiblePosition& visiblePosition)
104 {
105     m_base = visiblePosition.deepEquivalent();
106     validate();
107 }
108
109 void Selection::setExtent(const Position& position)
110 {
111     m_extent = position;
112     validate();
113 }
114
115 void Selection::setExtent(const VisiblePosition& visiblePosition)
116 {
117     m_extent = visiblePosition.deepEquivalent();
118     validate();
119 }
120
121 PassRefPtr<Range> Selection::toRange() const
122 {
123     if (isNone())
124         return 0;
125
126     // Make sure we have an updated layout since this function is called
127     // in the course of running edit commands which modify the DOM.
128     // Failing to call this can result in equivalentXXXPosition calls returning
129     // incorrect results.
130     m_start.node()->document()->updateLayout();
131
132     Position s, e;
133     if (isCaret()) {
134         // If the selection is a caret, move the range start upstream. This helps us match
135         // the conventions of text editors tested, which make style determinations based
136         // on the character before the caret, if any. 
137         s = rangeCompliantEquivalent(m_start.upstream());
138         e = s;
139     } else {
140         // If the selection is a range, select the minimum range that encompasses the selection.
141         // Again, this is to match the conventions of text editors tested, which make style 
142         // determinations based on the first character of the selection. 
143         // For instance, this operation helps to make sure that the "X" selected below is the 
144         // only thing selected. The range should not be allowed to "leak" out to the end of the 
145         // previous text node, or to the beginning of the next text node, each of which has a 
146         // different style.
147         // 
148         // On a treasure map, <b>X</b> marks the spot.
149         //                       ^ selected
150         //
151         ASSERT(isRange());
152         s = m_start.downstream();
153         e = m_end.upstream();
154         if (Range::compareBoundaryPoints(s.node(), s.offset(), e.node(), e.offset()) > 0) {
155             // Make sure the start is before the end.
156             // The end can wind up before the start if collapsed whitespace is the only thing selected.
157             Position tmp = s;
158             s = e;
159             e = tmp;
160         }
161         s = rangeCompliantEquivalent(s);
162         e = rangeCompliantEquivalent(e);
163     }
164
165     ExceptionCode ec = 0;
166     RefPtr<Range> result(new Range(s.node()->document()));
167     result->setStart(s.node(), s.offset(), ec);
168     if (ec) {
169         LOG_ERROR("Exception setting Range start from Selection: %d", ec);
170         return 0;
171     }
172     result->setEnd(e.node(), e.offset(), ec);
173     if (ec) {
174         LOG_ERROR("Exception setting Range end from Selection: %d", ec);
175         return 0;
176     }
177     return result.release();
178 }
179
180 bool Selection::expandUsingGranularity(TextGranularity granularity)
181 {
182     if (isNone())
183         return false;
184
185     m_granularity = granularity;
186     validate();
187     return true;
188 }
189
190 void Selection::validate()
191 {
192     // Move the selection to rendered positions, if possible.
193     bool baseAndExtentEqual = m_base == m_extent;
194     if (m_base.isNotNull()) {
195         m_base = VisiblePosition(m_base, m_affinity).deepEquivalent();
196         if (baseAndExtentEqual)
197             m_extent = m_base;
198     }
199     if (m_extent.isNotNull() && !baseAndExtentEqual)
200         m_extent = VisiblePosition(m_extent, m_affinity).deepEquivalent();
201
202     // Make sure we do not have a dangling base or extent.
203     if (m_base.isNull() && m_extent.isNull())
204         m_baseIsFirst = true;
205     else if (m_base.isNull()) {
206         m_base = m_extent;
207         m_baseIsFirst = true;
208     } else if (m_extent.isNull()) {
209         m_extent = m_base;
210         m_baseIsFirst = true;
211     } else {
212         m_baseIsFirst = comparePositions(m_base, m_extent) <= 0;
213     }
214
215     if (m_baseIsFirst) {
216         m_start = m_base;
217         m_end = m_extent;
218     } else {
219         m_start = m_extent;
220         m_end = m_base;
221     }
222
223     // Expand the selection if requested.
224     switch (m_granularity) {
225         case CharacterGranularity:
226             // Don't do any expansion.
227             break;
228         case WordGranularity: {
229             // General case: Select the word the caret is positioned inside of, or at the start of (RightWordIfOnBoundary).
230             // Edge case: If the caret is after the last word in a soft-wrapped line or the last word in
231             // the document, select that last word (LeftWordIfOnBoundary).
232             // Edge case: If the caret is after the last word in a paragraph, select from the the end of the
233             // last word to the line break (also RightWordIfOnBoundary);
234             VisiblePosition start = VisiblePosition(m_start, m_affinity);
235             VisiblePosition end   = VisiblePosition(m_end, m_affinity);
236             EWordSide side = RightWordIfOnBoundary;
237             if (isEndOfDocument(start) || (isEndOfLine(start) && !isStartOfLine(start) && !isEndOfParagraph(start)))
238                 side = LeftWordIfOnBoundary;
239             m_start = startOfWord(start, side).deepEquivalent();
240             side = RightWordIfOnBoundary;
241             if (isEndOfDocument(end) || (isEndOfLine(end) && !isStartOfLine(end) && !isEndOfParagraph(end)))
242                 side = LeftWordIfOnBoundary;
243             m_end = endOfWord(end, side).deepEquivalent();
244             break;
245         }
246         case SentenceGranularity: {
247             m_start = startOfSentence(VisiblePosition(m_start, m_affinity)).deepEquivalent();
248             m_end = endOfSentence(VisiblePosition(m_end, m_affinity)).deepEquivalent();
249             break;
250         }
251         case LineGranularity: {
252             m_start = startOfLine(VisiblePosition(m_start, m_affinity)).deepEquivalent();
253             VisiblePosition end = endOfLine(VisiblePosition(m_end, m_affinity));
254             // If the end of this line is at the end of a paragraph, include the space 
255             // after the end of the line in the selection.
256             if (isEndOfParagraph(end)) {
257                 VisiblePosition next = end.next();
258                 if (next.isNotNull())
259                     end = next;
260             }
261             m_end = end.deepEquivalent();
262             break;
263         }
264         case LineBoundary:
265             m_start = startOfLine(VisiblePosition(m_start, m_affinity)).deepEquivalent();
266             m_end = endOfLine(VisiblePosition(m_end, m_affinity)).deepEquivalent();
267             break;
268         case ParagraphGranularity: {
269             VisiblePosition pos(m_start, m_affinity);
270             if (isStartOfLine(pos) && isEndOfDocument(pos))
271                 pos = pos.previous();
272             m_start = startOfParagraph(pos).deepEquivalent();
273             VisiblePosition visibleParagraphEnd = endOfParagraph(VisiblePosition(m_end, m_affinity));
274             // Include the space after the end of the paragraph in the selection.
275             VisiblePosition startOfNextParagraph = visibleParagraphEnd.next();
276             if (startOfNextParagraph.isNull())
277                 m_end = visibleParagraphEnd.deepEquivalent();
278             else {
279                 m_end = startOfNextParagraph.deepEquivalent();
280                 // Stay within enclosing node, e.g. do not span end of table.
281                 if (visibleParagraphEnd.deepEquivalent().node()->isDescendantOf(m_end.node()))
282                     m_end = visibleParagraphEnd.deepEquivalent();
283             }
284             break;
285         }
286         case DocumentBoundary:
287             m_start = startOfDocument(VisiblePosition(m_start, m_affinity)).deepEquivalent();
288             m_end = endOfDocument(VisiblePosition(m_end, m_affinity)).deepEquivalent();
289             break;
290         case ParagraphBoundary:
291             m_start = startOfParagraph(VisiblePosition(m_start, m_affinity)).deepEquivalent();
292             m_end = endOfParagraph(VisiblePosition(m_end, m_affinity)).deepEquivalent();
293             break;
294         case SentenceBoundary:
295             m_start = startOfSentence(VisiblePosition(m_start, m_affinity)).deepEquivalent();
296             m_end = endOfSentence(VisiblePosition(m_end, m_affinity)).deepEquivalent();
297             break;
298     }
299     
300     // Make sure we do not have a dangling start or end.
301     if (m_start.isNull())
302         m_start = m_end;
303     if (m_end.isNull())
304         m_end = m_start;
305     
306     adjustForEditableContent();
307
308     // adjust the state
309     if (m_start.isNull()) {
310         ASSERT(m_end.isNull());
311         m_state = NONE;
312
313         // enforce downstream affinity if not caret, as affinity only
314         // makes sense for caret
315         m_affinity = DOWNSTREAM;
316     } else if (m_start == m_end || m_start.upstream() == m_end.upstream()) {
317         m_state = CARET;
318     } else {
319         m_state = RANGE;
320
321         // enforce downstream affinity if not caret, as affinity only
322         // makes sense for caret
323         m_affinity = DOWNSTREAM;
324
325         // "Constrain" the selection to be the smallest equivalent range of nodes.
326         // This is a somewhat arbitrary choice, but experience shows that it is
327         // useful to make to make the selection "canonical" (if only for
328         // purposes of comparing selections). This is an ideal point of the code
329         // to do this operation, since all selection changes that result in a RANGE 
330         // come through here before anyone uses it.
331         m_start = m_start.downstream();
332         m_end = m_end.upstream();
333     }
334 }
335
336 // FIXME: This function breaks the invariant of this class.
337 // But because we use Selection to store values in editing commands for use when
338 // undoing the command, we need to be able to create a selection that while currently
339 // invalid, will be valid once the changes are undone. This is a design problem.
340 // To fix it we either need to change the invariants of Selection or create a new
341 // class for editing to use that can manipulate selections that are not currently valid.
342 void Selection::setWithoutValidation(const Position& base, const Position& extent)
343 {
344     ASSERT(!base.isNull());
345     ASSERT(!extent.isNull());
346     ASSERT(base != extent);
347     ASSERT(m_affinity == DOWNSTREAM);
348     ASSERT(m_granularity == CharacterGranularity);
349     m_base = base;
350     m_extent = extent;
351     m_baseIsFirst = comparePositions(base, extent) <= 0;
352     if (m_baseIsFirst) {
353         m_start = base;
354         m_end = extent;
355     } else {
356         m_start = extent;
357         m_end = base;
358     }
359     m_state = RANGE;
360 }
361
362 void Selection::adjustForEditableContent()
363 {
364     if (m_base.isNull() || m_start.isNull() || m_end.isNull())
365         return;
366
367     Node* baseRoot = highestEditableRoot(m_base);
368     Node* startRoot = highestEditableRoot(m_start);
369     Node* endRoot = highestEditableRoot(m_end);
370     
371     Node* baseEditableAncestor = lowestEditableAncestor(m_base.node());
372     
373     // The base, start and end are all in the same region.  No adjustment necessary.
374     if (baseRoot == startRoot && baseRoot == endRoot)
375         return;
376     
377     // The selection is based in editable content.
378     if (baseRoot) {
379         // If the start is outside the base's editable root, cap it at the start of that root.
380         // If the start is in non-editable content that is inside the base's editable root, put it
381         // at the first editable position after start inside the base's editable root.
382         if (startRoot != baseRoot) {
383             VisiblePosition first = firstEditablePositionAfterPositionInRoot(m_start, baseRoot);
384             m_start = first.deepEquivalent();
385             if (m_start.isNull()) {
386                 ASSERT_NOT_REACHED();
387                 m_start = m_end;
388             }
389         }
390         // If the end is outside the base's editable root, cap it at the end of that root.
391         // If the end is in non-editable content that is inside the base's root, put it
392         // at the last editable position before the end inside the base's root.
393         if (endRoot != baseRoot) {
394             VisiblePosition last = lastEditablePositionBeforePositionInRoot(m_end, baseRoot);
395             m_end = last.deepEquivalent();
396             if (m_end.isNull()) {
397                 ASSERT_NOT_REACHED();
398                 m_end = m_start;
399             }
400         }
401     // The selection is based in non-editable content.
402     } else {
403         // FIXME: Non-editable pieces inside editable content should be atomic, in the same way that editable
404         // pieces in non-editable content are atomic.
405     
406         // The selection ends in editable content or non-editable content inside a different editable ancestor, 
407         // move backward until non-editable content inside the same lowest editable ancestor is reached.
408         Node* endEditableAncestor = lowestEditableAncestor(m_end.node());
409         if (endRoot || endEditableAncestor != baseEditableAncestor) {
410             
411             Position p = previousVisuallyDistinctCandidate(m_end);
412             Node* shadowAncestor = endRoot ? endRoot->shadowAncestorNode() : 0;
413             if (p.isNull() && endRoot && (shadowAncestor != endRoot))
414                 p = Position(shadowAncestor, maxDeepOffset(shadowAncestor));
415             while (p.isNotNull() && !(lowestEditableAncestor(p.node()) == baseEditableAncestor && !isEditablePosition(p))) {
416                 Node* root = editableRootForPosition(p);
417                 shadowAncestor = root ? root->shadowAncestorNode() : 0;
418                 p = isAtomicNode(p.node()) ? positionBeforeNode(p.node()) : previousVisuallyDistinctCandidate(p);
419                 if (p.isNull() && (shadowAncestor != root))
420                     p = Position(shadowAncestor, maxDeepOffset(shadowAncestor));
421             }
422             VisiblePosition previous(p);
423             
424             if (previous.isNull()) {
425                 ASSERT_NOT_REACHED();
426                 m_base = Position();
427                 m_extent = Position();
428                 validate();
429                 return;
430             }
431             m_end = previous.deepEquivalent();
432         }
433
434         // The selection starts in editable content or non-editable content inside a different editable ancestor, 
435         // move forward until non-editable content inside the same lowest editable ancestor is reached.
436         Node* startEditableAncestor = lowestEditableAncestor(m_start.node());      
437         if (startRoot || startEditableAncestor != baseEditableAncestor) {
438             Position p = nextVisuallyDistinctCandidate(m_start);
439             Node* shadowAncestor = startRoot ? startRoot->shadowAncestorNode() : 0;
440             if (p.isNull() && startRoot && (shadowAncestor != startRoot))
441                 p = Position(shadowAncestor, 0);
442             while (p.isNotNull() && !(lowestEditableAncestor(p.node()) == baseEditableAncestor && !isEditablePosition(p))) {
443                 Node* root = editableRootForPosition(p);
444                 shadowAncestor = root ? root->shadowAncestorNode() : 0;
445                 p = isAtomicNode(p.node()) ? positionAfterNode(p.node()) : nextVisuallyDistinctCandidate(p);
446                 if (p.isNull() && (shadowAncestor != root))
447                     p = Position(shadowAncestor, 0);
448             }
449             VisiblePosition next(p);
450             
451             if (next.isNull()) {
452                 ASSERT_NOT_REACHED();
453                 m_base = Position();
454                 m_extent = Position();
455                 validate();
456                 return;
457             }
458             m_start = next.deepEquivalent();
459         }
460     }
461     
462     // Correct the extent if necessary.
463     if (baseEditableAncestor != lowestEditableAncestor(m_extent.node()))
464         m_extent = m_baseIsFirst ? m_end : m_start;
465 }
466
467 bool Selection::isContentEditable() const
468 {
469     return isEditablePosition(start());
470 }
471
472 bool Selection::isContentRichlyEditable() const
473 {
474     return isRichlyEditablePosition(start());
475 }
476
477 Element* Selection::rootEditableElement() const
478 {
479     return editableRootForPosition(start());
480 }
481
482 void Selection::debugPosition() const
483 {
484     if (!m_start.node())
485         return;
486
487     fprintf(stderr, "Selection =================\n");
488
489     if (m_start == m_end) {
490         Position pos = m_start;
491         fprintf(stderr, "pos:        %s %p:%d\n", pos.node()->nodeName().deprecatedString().latin1(), pos.node(), pos.offset());
492     } else {
493         Position pos = m_start;
494         fprintf(stderr, "start:      %s %p:%d\n", pos.node()->nodeName().deprecatedString().latin1(), pos.node(), pos.offset());
495         fprintf(stderr, "-----------------------------------\n");
496         pos = m_end;
497         fprintf(stderr, "end:        %s %p:%d\n", pos.node()->nodeName().deprecatedString().latin1(), pos.node(), pos.offset());
498         fprintf(stderr, "-----------------------------------\n");
499     }
500
501     fprintf(stderr, "================================\n");
502 }
503
504 #ifndef NDEBUG
505
506 void Selection::formatForDebugger(char* buffer, unsigned length) const
507 {
508     String result;
509     String s;
510     
511     if (isNone()) {
512         result = "<none>";
513     } else {
514         const int FormatBufferSize = 1024;
515         char s[FormatBufferSize];
516         result += "from ";
517         start().formatForDebugger(s, FormatBufferSize);
518         result += s;
519         result += " to ";
520         end().formatForDebugger(s, FormatBufferSize);
521         result += s;
522     }
523
524     strncpy(buffer, result.deprecatedString().latin1(), length - 1);
525 }
526
527 void Selection::showTreeForThis() const
528 {
529     if (start().node()) {
530         start().node()->showTreeAndMark(start().node(), "S", end().node(), "E");
531         fprintf(stderr, "start offset: %d, end offset: %d\n", start().offset(), end().offset());
532     }
533 }
534
535 #endif
536
537 } // namespace WebCore
538
539 #ifndef NDEBUG
540
541 void showTree(const WebCore::Selection& sel)
542 {
543     sel.showTreeForThis();
544 }
545
546 void showTree(const WebCore::Selection* sel)
547 {
548     if (sel)
549         sel->showTreeForThis();
550 }
551
552 #endif