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