WebCore:
[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 originalEnd(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(originalEnd) || (isEndOfLine(originalEnd) && !isStartOfLine(originalEnd) && !isEndOfParagraph(originalEnd)))
242                 side = LeftWordIfOnBoundary;
243                 
244             VisiblePosition wordEnd(endOfWord(originalEnd, side));
245             VisiblePosition end(wordEnd);
246             
247             if (isEndOfParagraph(originalEnd)) {
248                 // Select the paragraph break (the space from the end of a paragraph to the start of
249                 // the next one) to match TextEdit.
250                 end = wordEnd.next(true);
251                 
252                 if (Node* table = isFirstPositionAfterTable(end)) {
253                     // The paragraph break after the last paragraph in the last cell of a block table ends
254                     // at the start of the paragraph after the table.
255                     if (isBlock(table))
256                         end = end.next(true);
257                     else
258                         end = wordEnd;
259                 }
260                 
261                 if (end.isNull())
262                     end = wordEnd;
263             }
264             
265             m_end = end.deepEquivalent();
266             break;
267         }
268         case SentenceGranularity: {
269             m_start = startOfSentence(VisiblePosition(m_start, m_affinity)).deepEquivalent();
270             m_end = endOfSentence(VisiblePosition(m_end, m_affinity)).deepEquivalent();
271             break;
272         }
273         case LineGranularity: {
274             m_start = startOfLine(VisiblePosition(m_start, m_affinity)).deepEquivalent();
275             VisiblePosition end = endOfLine(VisiblePosition(m_end, m_affinity));
276             // If the end of this line is at the end of a paragraph, include the space 
277             // after the end of the line in the selection.
278             if (isEndOfParagraph(end)) {
279                 VisiblePosition next = end.next();
280                 if (next.isNotNull())
281                     end = next;
282             }
283             m_end = end.deepEquivalent();
284             break;
285         }
286         case LineBoundary:
287             m_start = startOfLine(VisiblePosition(m_start, m_affinity)).deepEquivalent();
288             m_end = endOfLine(VisiblePosition(m_end, m_affinity)).deepEquivalent();
289             break;
290         case ParagraphGranularity: {
291             VisiblePosition pos(m_start, m_affinity);
292             if (isStartOfLine(pos) && isEndOfDocument(pos))
293                 pos = pos.previous();
294             m_start = startOfParagraph(pos).deepEquivalent();
295             VisiblePosition visibleParagraphEnd = endOfParagraph(VisiblePosition(m_end, m_affinity));
296             // Include the space after the end of the paragraph in the selection.
297             VisiblePosition startOfNextParagraph = visibleParagraphEnd.next();
298             if (startOfNextParagraph.isNull())
299                 m_end = visibleParagraphEnd.deepEquivalent();
300             else {
301                 m_end = startOfNextParagraph.deepEquivalent();
302                 // Stay within enclosing node, e.g. do not span end of table.
303                 if (visibleParagraphEnd.deepEquivalent().node()->isDescendantOf(m_end.node()))
304                     m_end = visibleParagraphEnd.deepEquivalent();
305             }
306             
307             // Include the "paragraph break" (the space from the end of this paragraph to the start
308             // of the next one) in the selection.
309             VisiblePosition end(visibleParagraphEnd.next(true));
310             
311             if (Node* table = isFirstPositionAfterTable(end)) {
312                 // The paragraph break after the last paragraph in the last cell of a block table ends
313                 // at the start of the paragraph after the table, not at the position just after the table.
314                 if (isBlock(table))
315                     end = end.next(true);
316                 // There is no parargraph break after the last paragraph in the last cell of an inline table.
317                 else
318                     end = visibleParagraphEnd;
319             }
320             
321             if (end.isNull())
322                 end = visibleParagraphEnd;
323
324             m_end = end.deepEquivalent();
325             break;
326         }
327         case DocumentBoundary:
328             m_start = startOfDocument(VisiblePosition(m_start, m_affinity)).deepEquivalent();
329             m_end = endOfDocument(VisiblePosition(m_end, m_affinity)).deepEquivalent();
330             break;
331         case ParagraphBoundary:
332             m_start = startOfParagraph(VisiblePosition(m_start, m_affinity)).deepEquivalent();
333             m_end = endOfParagraph(VisiblePosition(m_end, m_affinity)).deepEquivalent();
334             break;
335         case SentenceBoundary:
336             m_start = startOfSentence(VisiblePosition(m_start, m_affinity)).deepEquivalent();
337             m_end = endOfSentence(VisiblePosition(m_end, m_affinity)).deepEquivalent();
338             break;
339     }
340     
341     // Make sure we do not have a dangling start or end.
342     if (m_start.isNull())
343         m_start = m_end;
344     if (m_end.isNull())
345         m_end = m_start;
346     
347     adjustForEditableContent();
348
349     // adjust the state
350     if (m_start.isNull()) {
351         ASSERT(m_end.isNull());
352         m_state = NONE;
353
354         // enforce downstream affinity if not caret, as affinity only
355         // makes sense for caret
356         m_affinity = DOWNSTREAM;
357     } else if (m_start == m_end || m_start.upstream() == m_end.upstream()) {
358         m_state = CARET;
359     } else {
360         m_state = RANGE;
361
362         // enforce downstream affinity if not caret, as affinity only
363         // makes sense for caret
364         m_affinity = DOWNSTREAM;
365
366         // "Constrain" the selection to be the smallest equivalent range of nodes.
367         // This is a somewhat arbitrary choice, but experience shows that it is
368         // useful to make to make the selection "canonical" (if only for
369         // purposes of comparing selections). This is an ideal point of the code
370         // to do this operation, since all selection changes that result in a RANGE 
371         // come through here before anyone uses it.
372         m_start = m_start.downstream();
373         m_end = m_end.upstream();
374     }
375 }
376
377 // FIXME: This function breaks the invariant of this class.
378 // But because we use Selection to store values in editing commands for use when
379 // undoing the command, we need to be able to create a selection that while currently
380 // invalid, will be valid once the changes are undone. This is a design problem.
381 // To fix it we either need to change the invariants of Selection or create a new
382 // class for editing to use that can manipulate selections that are not currently valid.
383 void Selection::setWithoutValidation(const Position& base, const Position& extent)
384 {
385     ASSERT(!base.isNull());
386     ASSERT(!extent.isNull());
387     ASSERT(base != extent);
388     ASSERT(m_affinity == DOWNSTREAM);
389     ASSERT(m_granularity == CharacterGranularity);
390     m_base = base;
391     m_extent = extent;
392     m_baseIsFirst = comparePositions(base, extent) <= 0;
393     if (m_baseIsFirst) {
394         m_start = base;
395         m_end = extent;
396     } else {
397         m_start = extent;
398         m_end = base;
399     }
400     m_state = RANGE;
401 }
402
403 void Selection::adjustForEditableContent()
404 {
405     if (m_base.isNull() || m_start.isNull() || m_end.isNull())
406         return;
407
408     Node* baseRoot = highestEditableRoot(m_base);
409     Node* startRoot = highestEditableRoot(m_start);
410     Node* endRoot = highestEditableRoot(m_end);
411     
412     Node* baseEditableAncestor = lowestEditableAncestor(m_base.node());
413     
414     // The base, start and end are all in the same region.  No adjustment necessary.
415     if (baseRoot == startRoot && baseRoot == endRoot)
416         return;
417     
418     // The selection is based in editable content.
419     if (baseRoot) {
420         // If the start is outside the base's editable root, cap it at the start of that root.
421         // If the start is in non-editable content that is inside the base's editable root, put it
422         // at the first editable position after start inside the base's editable root.
423         if (startRoot != baseRoot) {
424             VisiblePosition first = firstEditablePositionAfterPositionInRoot(m_start, baseRoot);
425             m_start = first.deepEquivalent();
426             if (m_start.isNull()) {
427                 ASSERT_NOT_REACHED();
428                 m_start = m_end;
429             }
430         }
431         // If the end is outside the base's editable root, cap it at the end of that root.
432         // If the end is in non-editable content that is inside the base's root, put it
433         // at the last editable position before the end inside the base's root.
434         if (endRoot != baseRoot) {
435             VisiblePosition last = lastEditablePositionBeforePositionInRoot(m_end, baseRoot);
436             m_end = last.deepEquivalent();
437             if (m_end.isNull()) {
438                 ASSERT_NOT_REACHED();
439                 m_end = m_start;
440             }
441         }
442     // The selection is based in non-editable content.
443     } else {
444         // FIXME: Non-editable pieces inside editable content should be atomic, in the same way that editable
445         // pieces in non-editable content are atomic.
446     
447         // The selection ends in editable content or non-editable content inside a different editable ancestor, 
448         // move backward until non-editable content inside the same lowest editable ancestor is reached.
449         Node* endEditableAncestor = lowestEditableAncestor(m_end.node());
450         if (endRoot || endEditableAncestor != baseEditableAncestor) {
451             
452             Position p = previousVisuallyDistinctCandidate(m_end);
453             Node* shadowAncestor = endRoot ? endRoot->shadowAncestorNode() : 0;
454             if (p.isNull() && endRoot && (shadowAncestor != endRoot))
455                 p = Position(shadowAncestor, maxDeepOffset(shadowAncestor));
456             while (p.isNotNull() && !(lowestEditableAncestor(p.node()) == baseEditableAncestor && !isEditablePosition(p))) {
457                 Node* root = editableRootForPosition(p);
458                 shadowAncestor = root ? root->shadowAncestorNode() : 0;
459                 p = isAtomicNode(p.node()) ? positionBeforeNode(p.node()) : previousVisuallyDistinctCandidate(p);
460                 if (p.isNull() && (shadowAncestor != root))
461                     p = Position(shadowAncestor, maxDeepOffset(shadowAncestor));
462             }
463             VisiblePosition previous(p);
464             
465             if (previous.isNull()) {
466                 ASSERT_NOT_REACHED();
467                 m_base = Position();
468                 m_extent = Position();
469                 validate();
470                 return;
471             }
472             m_end = previous.deepEquivalent();
473         }
474
475         // The selection starts in editable content or non-editable content inside a different editable ancestor, 
476         // move forward until non-editable content inside the same lowest editable ancestor is reached.
477         Node* startEditableAncestor = lowestEditableAncestor(m_start.node());      
478         if (startRoot || startEditableAncestor != baseEditableAncestor) {
479             Position p = nextVisuallyDistinctCandidate(m_start);
480             Node* shadowAncestor = startRoot ? startRoot->shadowAncestorNode() : 0;
481             if (p.isNull() && startRoot && (shadowAncestor != startRoot))
482                 p = Position(shadowAncestor, 0);
483             while (p.isNotNull() && !(lowestEditableAncestor(p.node()) == baseEditableAncestor && !isEditablePosition(p))) {
484                 Node* root = editableRootForPosition(p);
485                 shadowAncestor = root ? root->shadowAncestorNode() : 0;
486                 p = isAtomicNode(p.node()) ? positionAfterNode(p.node()) : nextVisuallyDistinctCandidate(p);
487                 if (p.isNull() && (shadowAncestor != root))
488                     p = Position(shadowAncestor, 0);
489             }
490             VisiblePosition next(p);
491             
492             if (next.isNull()) {
493                 ASSERT_NOT_REACHED();
494                 m_base = Position();
495                 m_extent = Position();
496                 validate();
497                 return;
498             }
499             m_start = next.deepEquivalent();
500         }
501     }
502     
503     // Correct the extent if necessary.
504     if (baseEditableAncestor != lowestEditableAncestor(m_extent.node()))
505         m_extent = m_baseIsFirst ? m_end : m_start;
506 }
507
508 bool Selection::isContentEditable() const
509 {
510     return isEditablePosition(start());
511 }
512
513 bool Selection::isContentRichlyEditable() const
514 {
515     return isRichlyEditablePosition(start());
516 }
517
518 Element* Selection::rootEditableElement() const
519 {
520     return editableRootForPosition(start());
521 }
522
523 void Selection::debugPosition() const
524 {
525     if (!m_start.node())
526         return;
527
528     fprintf(stderr, "Selection =================\n");
529
530     if (m_start == m_end) {
531         Position pos = m_start;
532         fprintf(stderr, "pos:        %s %p:%d\n", pos.node()->nodeName().deprecatedString().latin1(), pos.node(), pos.offset());
533     } else {
534         Position pos = m_start;
535         fprintf(stderr, "start:      %s %p:%d\n", pos.node()->nodeName().deprecatedString().latin1(), pos.node(), pos.offset());
536         fprintf(stderr, "-----------------------------------\n");
537         pos = m_end;
538         fprintf(stderr, "end:        %s %p:%d\n", pos.node()->nodeName().deprecatedString().latin1(), pos.node(), pos.offset());
539         fprintf(stderr, "-----------------------------------\n");
540     }
541
542     fprintf(stderr, "================================\n");
543 }
544
545 #ifndef NDEBUG
546
547 void Selection::formatForDebugger(char* buffer, unsigned length) const
548 {
549     String result;
550     String s;
551     
552     if (isNone()) {
553         result = "<none>";
554     } else {
555         const int FormatBufferSize = 1024;
556         char s[FormatBufferSize];
557         result += "from ";
558         start().formatForDebugger(s, FormatBufferSize);
559         result += s;
560         result += " to ";
561         end().formatForDebugger(s, FormatBufferSize);
562         result += s;
563     }
564
565     strncpy(buffer, result.deprecatedString().latin1(), length - 1);
566 }
567
568 void Selection::showTreeForThis() const
569 {
570     if (start().node()) {
571         start().node()->showTreeAndMark(start().node(), "S", end().node(), "E");
572         fprintf(stderr, "start offset: %d, end offset: %d\n", start().offset(), end().offset());
573     }
574 }
575
576 #endif
577
578 } // namespace WebCore
579
580 #ifndef NDEBUG
581
582 void showTree(const WebCore::Selection& sel)
583 {
584     sel.showTreeForThis();
585 }
586
587 void showTree(const WebCore::Selection* sel)
588 {
589     if (sel)
590         sel->showTreeForThis();
591 }
592
593 #endif