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