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