WebCore/khtml/editing/visible_position.cpp

   1 /*
   2  * Copyright (C) 2004 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 "visible_position.h"
  27
  28 #include "misc/htmltags.h"
  29 #include "rendering/render_line.h"
  30 #include "rendering/render_object.h"
  31 #include "rendering/render_text.h"
  32 #include "xml/dom2_rangeimpl.h"
  33 #include "xml/dom_nodeimpl.h"
  34 #include "xml/dom_textimpl.h"
  35
  36 #if APPLE_CHANGES
  37 #include "KWQAssertions.h"
  38 #include "KWQLogging.h"
  39 #else
  40 #define ASSERT(assertion) assert(assertion)
  41 #define LOG(channel, formatAndArgs...) ((void)0)
  42 #endif
  43
  44 using DOM::CharacterDataImpl;
  45 using DOM::NodeImpl;
  46 using DOM::offsetInCharacters;
  47 using DOM::UsingComposedCharacters;
  48 using DOM::Position;
  49 using DOM::Range;
  50 using DOM::RangeImpl;
  51 using DOM::TextImpl;
  52
  53 namespace khtml {
  54
  55 VisiblePosition::VisiblePosition(const Position &pos, EAffinity affinity, EInitHint initHint)
  56 {
  57     init(pos, initHint, affinity);
  58 }
  59
  60 VisiblePosition::VisiblePosition(NodeImpl *node, long offset, EAffinity affinity, EInitHint initHint)
  61 {
  62     init(Position(node, offset), initHint, affinity);
  63 }
  64
  65 VisiblePosition::VisiblePosition(const VisiblePosition &other)
  66 {
  67     m_deepPosition = other.m_deepPosition;
  68     m_affinity = other.m_affinity;
  69 }
  70
  71 void VisiblePosition::init(const Position &pos, EInitHint initHint, EAffinity affinity)
  72 {
  73     m_affinity = affinity;
  74
  75     // A first step toward eliminating the initHint parameter.
  76     // For <br> 0, it's important not to move past the <br>.
  77     if (pos.node() && pos.node()->id() == ID_BR && pos.offset() == 0)
  78         initHint = INIT_UP;
  79
  80     switch (initHint) {
  81         case INIT_UP:
  82             initUpstream(pos);
  83             break;
  84         case INIT_DOWN:
  85             initDownstream(pos);
  86             break;
  87         default:
  88             ASSERT_NOT_REACHED();
  89             break;
  90     }
  91 }
  92
  93 void VisiblePosition::initUpstream(const Position &pos)
  94 {
  95     Position deepPos = deepEquivalent(pos);
  96
  97     if (isCandidate(deepPos)) {
  98         m_deepPosition = deepPos;
  99         Position next = nextVisiblePosition(deepPos);
 100         if (next.isNotNull()) {
 101             Position previous = previousVisiblePosition(next);
 102             if (previous.isNotNull())
 103                 m_deepPosition = previous;
 104         }
 105     }
 106     else {
 107         Position previous = previousVisiblePosition(deepPos);
 108         if (previous.isNotNull()) {
 109             m_deepPosition = previous;
 110         } else {
 111             Position next = nextVisiblePosition(deepPos);
 112             if (next.isNotNull())
 113                 m_deepPosition = next;
 114         }
 115     }
 116 }
 117
 118 static bool isRenderedBR(NodeImpl *node)
 119 {
 120     if (!node)
 121         return false;
 122
 123     RenderObject *renderer = node->renderer();
 124     if (!renderer)
 125         return false;
 126
 127     if (renderer->style()->visibility() != VISIBLE)
 128         return false;
 129
 130     if (renderer->isBR())
 131         return true;
 132
 133     return false;
 134 }
 135
 136 void VisiblePosition::initDownstream(const Position &pos)
 137 {
 138     Position deepPos = deepEquivalent(pos);
 139
 140     if (isCandidate(deepPos)) {
 141         m_deepPosition = deepPos;
 142         Position previous = previousVisiblePosition(deepPos);
 143         if (previous.isNotNull()) {
 144             Position next = nextVisiblePosition(previous);
 145             if (next.isNotNull())
 146                 m_deepPosition = next;
 147         }
 148     } else {
 149         Position next = nextVisiblePosition(deepPos);
 150         if (next.isNotNull()) {
 151             m_deepPosition = next;
 152         } else if (isRenderedBR(deepPos.node()) && deepPos.offset() == 1) {
 153             m_deepPosition = deepPos;
 154         } else {
 155             Position previous = previousVisiblePosition(deepPos);
 156             if (previous.isNotNull())
 157                 m_deepPosition = previous;
 158         }
 159     }
 160 }
 161
 162 VisiblePosition VisiblePosition::next() const
 163 {
 164     VisiblePosition result = VisiblePosition(nextVisiblePosition(m_deepPosition), m_affinity);
 165     setAffinityUsingLinePosition(result);
 166     return result;
 167 }
 168
 169 VisiblePosition VisiblePosition::previous() const
 170 {
 171     VisiblePosition result =  VisiblePosition(previousVisiblePosition(m_deepPosition), DOWNSTREAM);
 172
 173 #ifndef NDEBUG
 174     // we should always be able to make the affinity DOWNSTREAM, because going previous from an
 175     // UPSTREAM position can never yield another UPSTREAM position (unless line wrap length is 0!).
 176     if (result.isNotNull() && m_affinity == UPSTREAM) {
 177         VisiblePosition temp = result;
 178         temp.setAffinity(UPSTREAM);
 179         ASSERT(!visiblePositionsOnDifferentLines(temp, result));
 180     }
 181 #endif
 182     return result;
 183 }
 184
 185 Position VisiblePosition::previousVisiblePosition(const Position &pos)
 186 {
 187     if (pos.isNull() || pos.atStart())
 188         return Position();
 189
 190     Position test = deepEquivalent(pos);
 191     Position downstreamTest = test.downstream();
 192     bool acceptAnyVisiblePosition = !isCandidate(test);
 193
 194     Position current = test;
 195     while (!current.atStart()) {
 196         current = current.previous(UsingComposedCharacters);
 197         if (isCandidate(current) && (acceptAnyVisiblePosition || (downstreamTest != current.downstream()))) {
 198             return current;
 199         }
 200     }
 201
 202     return Position();
 203 }
 204
 205 Position VisiblePosition::nextVisiblePosition(const Position &pos)
 206 {
 207     if (pos.isNull() || pos.atEnd())
 208         return Position();
 209
 210     Position test = deepEquivalent(pos);
 211     bool acceptAnyVisiblePosition = !isCandidate(test);
 212
 213     Position current = test;
 214     Position downstreamTest = test.downstream();
 215     while (!current.atEnd()) {
 216         current = current.next(UsingComposedCharacters);
 217         if (isCandidate(current) && (acceptAnyVisiblePosition || (downstreamTest != current.downstream()))) {
 218             return current;
 219         }
 220     }
 221
 222     return Position();
 223 }
 224
 225 bool VisiblePosition::isCandidate(const Position &pos)
 226 {
 227     if (pos.isNull())
 228         return false;
 229
 230     RenderObject *renderer = pos.node()->renderer();
 231     if (!renderer)
 232         return false;
 233
 234     if (renderer->style()->visibility() != VISIBLE)
 235         return false;
 236
 237     if (renderer->isReplaced())
 238         // return true for replaced elements
 239         return pos.offset() == 0 || pos.offset() == 1;
 240
 241     if (renderer->isBR()) {
 242         if (pos.offset() == 0) {
 243             InlineBox* box = static_cast<RenderText*>(renderer)->firstTextBox();
 244             if (box) {
 245                 // return true for offset 0 into BR element on a line by itself
 246                 RootInlineBox* root = box->root();
 247                 if (root)
 248                     return root->firstLeafChild() == box && root->lastLeafChild() == box;
 249             }
 250         }
 251         return false;
 252     }
 253
 254     if (renderer->isText()) {
 255         RenderText *textRenderer = static_cast<RenderText *>(renderer);
 256         for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
 257             if (pos.offset() >= box->m_start && pos.offset() <= box->m_start + box->m_len) {
 258                 // return true if in a text node
 259                 return true;
 260             }
 261         }
 262     }
 263
 264     if (renderer->isBlockFlow() && (!renderer->firstChild() || !pos.node()->firstChild()) &&
 265        (renderer->height() || pos.node()->id() == ID_BODY)) {
 266         // return true for offset 0 into rendered blocks that are empty of rendered kids, but have a height
 267         return pos.offset() == 0;
 268     }
 269
 270     return false;
 271 }
 272
 273 Position VisiblePosition::deepEquivalent(const Position &pos)
 274 {
 275     NodeImpl *node = pos.node();
 276     long offset = pos.offset();
 277
 278     if (!node)
 279         return Position();
 280
 281     if (isAtomicNode(node))
 282         return pos;
 283
 284     if (offset >= (long)node->childNodeCount()) {
 285         do {
 286             NodeImpl *child = node->lastChild();
 287             if (!child)
 288                 break;
 289             node = child;
 290         } while (!isAtomicNode(node));
 291         return Position(node, node->caretMaxOffset());
 292     }
 293
 294     node = node->childNode(offset);
 295     ASSERT(node);
 296     while (!isAtomicNode(node)) {
 297         NodeImpl *child = node->firstChild();
 298         if (!child)
 299             break;
 300         node = child;
 301     }
 302     return Position(node, 0);
 303 }
 304
 305 Position VisiblePosition::downstreamDeepEquivalent() const
 306 {
 307     Position pos = m_deepPosition;
 308
 309     if (pos.isNull() || pos.atEnd())
 310         return pos;
 311
 312     Position downstreamTest = pos.downstream();
 313
 314     Position current = pos;
 315     while (!current.atEnd()) {
 316         current = current.next(UsingComposedCharacters);
 317         if (isCandidate(current)) {
 318             if (downstreamTest != current.downstream())
 319                 break;
 320             pos = current;
 321         }
 322     }
 323
 324     return pos;
 325 }
 326
 327 Position VisiblePosition::rangeCompliantEquivalent(const Position &pos)
 328 {
 329     NodeImpl *node = pos.node();
 330     if (!node)
 331         return Position();
 332
 333     // FIXME: This clamps out-of-range values.
 334     // Instead we should probably assert, and not use such values.
 335
 336     long offset = pos.offset();
 337     if (!offsetInCharacters(node->nodeType()) && isAtomicNode(node) && offset > 0)
 338         return Position(node->parentNode(), node->nodeIndex() + 1);
 339
 340     return Position(node, kMax(0L, kMin(offset, maxOffset(node))));
 341 }
 342
 343 long VisiblePosition::maxOffset(const NodeImpl *node)
 344 {
 345     return offsetInCharacters(node->nodeType()) ? (long)static_cast<const CharacterDataImpl *>(node)->length() : (long)node->childNodeCount();
 346 }
 347
 348 bool VisiblePosition::isAtomicNode(const NodeImpl *node)
 349 {
 350     return node && (!node->hasChildNodes() || (node->id() == ID_OBJECT && node->renderer() && node->renderer()->isReplaced()));
 351 }
 352
 353 QChar VisiblePosition::character() const
 354 {
 355     Position pos = position();
 356     NodeImpl *node = pos.node();
 357     if (!node || !node->isTextNode()) {
 358         return QChar();
 359     }
 360     TextImpl *textNode = static_cast<TextImpl *>(pos.node());
 361     long offset = pos.offset();
 362     if ((unsigned)offset >= textNode->length()) {
 363         return QChar();
 364     }
 365     return textNode->data()[offset];
 366 }
 367
 368 bool isEqualIgnoringAffinity(const VisiblePosition &a, const VisiblePosition &b)
 369 {
 370     bool result = a.m_deepPosition == b.m_deepPosition;
 371     if (result) {
 372         // We want to catch cases where positions are equal, but affinities are not, since
 373         // this is very likely a bug, given the places where this call is used. The difference
 374         // is very likely due to code that set the affinity on a VisiblePosition "by hand" and
 375         // did so incorrectly.
 376         ASSERT(a.m_affinity == b.m_affinity);
 377     }
 378     return result;
 379 }
 380
 381 bool isNotEqualIgnoringAffinity(const VisiblePosition &a, const VisiblePosition &b)
 382 {
 383     return !isEqualIgnoringAffinity(a, b);
 384 }
 385
 386 void VisiblePosition::debugPosition(const char *msg) const
 387 {
 388     if (isNull())
 389         fprintf(stderr, "Position [%s]: null\n", msg);
 390     else
 391         fprintf(stderr, "Position [%s]: %s [%p] at %ld\n", msg, m_deepPosition.node()->nodeName().string().latin1(), m_deepPosition.node(), m_deepPosition.offset());
 392 }
 393
 394 #ifndef NDEBUG
 395 void VisiblePosition::formatForDebugger(char *buffer, unsigned length) const
 396 {
 397     m_deepPosition.formatForDebugger(buffer, length);
 398 }
 399 #endif
 400
 401 Range makeRange(const VisiblePosition &start, const VisiblePosition &end)
 402 {
 403     Position s = start.position();
 404     Position e = end.position();
 405     return Range(s.node(), s.offset(), e.node(), e.offset());
 406 }
 407
 408 VisiblePosition startVisiblePosition(const Range &r, EAffinity affinity)
 409 {
 410     return VisiblePosition(r.startContainer().handle(), r.startOffset(), affinity);
 411 }
 412
 413 VisiblePosition endVisiblePosition(const Range &r, EAffinity affinity)
 414 {
 415     return VisiblePosition(r.endContainer().handle(), r.endOffset(), affinity);
 416 }
 417
 418 bool setStart(Range &r, const VisiblePosition &c)
 419 {
 420     RangeImpl *ri = r.handle();
 421     if (!ri)
 422         return false;
 423     Position p = c.position();
 424     int code = 0;
 425     ri->setStart(p.node(), p.offset(), code);
 426     return code == 0;
 427 }
 428
 429 bool setEnd(Range &r, const VisiblePosition &c)
 430 {
 431     RangeImpl *ri = r.handle();
 432     if (!ri)
 433         return false;
 434     Position p = c.position();
 435     int code = 0;
 436     ri->setEnd(p.node(), p.offset(), code);
 437     return code == 0;
 438 }
 439
 440 void setAffinityUsingLinePosition(VisiblePosition &pos)
 441 {
 442     // When not moving across line wrap, make sure to end up with DOWNSTREAM affinity.
 443     if (pos.isNotNull() && pos.affinity() == UPSTREAM) {
 444         VisiblePosition temp(pos);
 445         temp.setAffinity(DOWNSTREAM);
 446         if (!visiblePositionsOnDifferentLines(temp, pos))
 447             pos.setAffinity(DOWNSTREAM);
 448     }
 449 }
 450
 451 DOM::NodeImpl *enclosingBlockFlowElement(const VisiblePosition &vp)
 452 {
 453     if (vp.isNull())
 454         return NULL;
 455
 456     return vp.position().node()->enclosingBlockFlowElement();
 457 }
 458
 459 bool visiblePositionsOnDifferentLines(const VisiblePosition &pos1, const VisiblePosition &pos2)
 460 {
 461     if (pos1.isNull() || pos2.isNull())
 462         return false;
 463     if (pos1 == pos2)
 464         return false;
 465
 466     Position p1 = pos1.deepEquivalent();
 467     Position p2 = pos2.deepEquivalent();
 468     RenderObject *r1 = p1.node()->renderer();
 469     RenderObject *r2 = p2.node()->renderer();
 470     if (r1->isBlockFlow() || r2->isBlockFlow())
 471         return r1 == r2 ? false : true;
 472     InlineBox *b1 = r1 ? r1->inlineBox(p1.offset(), pos1.affinity()) : 0;
 473     InlineBox *b2 = r2 ? r2->inlineBox(p2.offset(), pos2.affinity()) : 0;
 474     return (b1 && b2 && b1->root() != b2->root());
 475 }
 476
 477 enum EBlockRelationship {
 478     NoBlockRelationship,
 479     SameBlockRelationship,
 480     PeerBlockRelationship,
 481     AncestorBlockRelationship,
 482     DescendantBlockRelationship,
 483     OtherBlockRelationship
 484 };
 485
 486 static EBlockRelationship blockRelationship(const VisiblePosition &pos1, const VisiblePosition &pos2)
 487 {
 488     if (pos1.isNull() || pos2.isNull())
 489         return NoBlockRelationship;
 490     if (pos1 == pos2)
 491         return SameBlockRelationship;
 492
 493     Position p1 = pos1.deepEquivalent();
 494     Position p2 = pos2.deepEquivalent();
 495     NodeImpl *b1 = p1.node()->enclosingBlockFlowElement();
 496     NodeImpl *b2 = p2.node()->enclosingBlockFlowElement();
 497     if (!b1 || !b2)
 498         return NoBlockRelationship;
 499     if (b1 == b2)
 500         return SameBlockRelationship;
 501     if (b1->parentNode() == b2->parentNode())
 502         return PeerBlockRelationship;
 503     if (b2->isAncestor(b1))
 504         return AncestorBlockRelationship;
 505     if (b1->isAncestor(b2))
 506         return DescendantBlockRelationship;
 507     return OtherBlockRelationship;
 508 }
 509
 510 bool visiblePositionsInDifferentBlocks(const VisiblePosition &pos1, const VisiblePosition &pos2)
 511 {
 512     switch (blockRelationship(pos1, pos2)) {
 513         case NoBlockRelationship:
 514         case SameBlockRelationship:
 515             return false;
 516         case PeerBlockRelationship:
 517         case AncestorBlockRelationship:
 518         case DescendantBlockRelationship:
 519         case OtherBlockRelationship:
 520             return true;
 521     }
 522     ASSERT_NOT_REACHED();
 523     return false;
 524 }
 525
 526 bool isFirstVisiblePositionOnLine(const VisiblePosition &pos)
 527 {
 528     if (pos.isNull())
 529         return false;
 530
 531     VisiblePosition previous = pos.previous();
 532     return previous.isNull() || visiblePositionsOnDifferentLines(pos, previous);
 533 }
 534
 535 bool isFirstVisiblePositionInParagraph(const VisiblePosition &pos)
 536 {
 537     if (pos.isNull())
 538         return false;
 539
 540     return pos.deepEquivalent().upstream().node()->id() == ID_BR || isFirstVisiblePositionInBlock(pos);
 541 }
 542
 543 bool isFirstVisiblePositionInBlock(const VisiblePosition &pos)
 544 {
 545     if (pos.isNull())
 546         return false;
 547
 548     Position upstream = pos.deepEquivalent().upstream();
 549     return upstream.node()->isBlockFlow() && upstream.offset() == 0;
 550 }
 551
 552 bool isFirstVisiblePositionInNode(const VisiblePosition &pos, const NodeImpl *node)
 553 {
 554     if (pos.isNull())
 555         return false;
 556
 557     VisiblePosition previous = pos.previous();
 558     return previous.isNull() || !previous.deepEquivalent().node()->isAncestor(node);
 559 }
 560
 561 bool isLastVisiblePositionOnLine(const VisiblePosition &pos)
 562 {
 563     if (pos.isNull())
 564         return false;
 565
 566     VisiblePosition next = pos.next();
 567     return next.isNull() || visiblePositionsOnDifferentLines(pos, next);
 568 }
 569
 570 bool isLastVisiblePositionInParagraph(const VisiblePosition &pos)
 571 {
 572     if (pos.isNull())
 573         return false;
 574
 575     return pos.deepEquivalent().downstream().node()->id() == ID_BR || isLastVisiblePositionInBlock(pos);
 576 }
 577
 578 bool isLastVisiblePositionInBlock(const VisiblePosition &pos)
 579 {
 580     if (pos.isNull())
 581         return false;
 582
 583     VisiblePosition next = pos.next();
 584     if (next.isNull())
 585         return true;
 586
 587     switch (blockRelationship(pos, next)) {
 588         case NoBlockRelationship:
 589         case SameBlockRelationship:
 590         case AncestorBlockRelationship:
 591             return false;
 592         case OtherBlockRelationship:
 593         case PeerBlockRelationship:
 594         case DescendantBlockRelationship:
 595             return true;
 596     }
 597     ASSERT_NOT_REACHED();
 598     return false;
 599 }
 600
 601 bool isLastVisiblePositionInNode(const VisiblePosition &pos, const NodeImpl *node)
 602 {
 603     if (pos.isNull())
 604         return false;
 605
 606     VisiblePosition next = pos.next();
 607     return next.isNull() || !next.deepEquivalent().node()->isAncestor(node);
 608 }
 609
 610 }  // namespace DOM