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