1/* 2 * (C) 1999 Lars Knoll (knoll@kde.org) 3 * (C) 2000 Gunnstein Lye (gunnstein@netcom.no) 4 * (C) 2000 Frederik Holljen (frederik.holljen@hig.no) 5 * (C) 2001 Peter Kelly (pmk@post.com) 6 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved. 7 * Copyright (C) 2011 Motorola Mobility. All rights reserved. 8 * 9 * This library is free software; you can redistribute it and/or 10 * modify it under the terms of the GNU Library General Public 11 * License as published by the Free Software Foundation; either 12 * version 2 of the License, or (at your option) any later version. 13 * 14 * This library is distributed in the hope that it will be useful, 15 * but WITHOUT ANY WARRANTY; without even the implied warranty of 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17 * Library General Public License for more details. 18 * 19 * You should have received a copy of the GNU Library General Public License 20 * along with this library; see the file COPYING.LIB. If not, write to 21 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 22 * Boston, MA 02110-1301, USA. 23 */ 24 25#include "config.h" 26#include "Range.h" 27 28#include "ClientRect.h" 29#include "ClientRectList.h" 30#include "DocumentFragment.h" 31#include "Frame.h" 32#include "FrameView.h" 33#include "HTMLElement.h" 34#include "HTMLNames.h" 35#include "NodeTraversal.h" 36#include "NodeWithIndex.h" 37#include "Page.h" 38#include "ProcessingInstruction.h" 39#include "RangeException.h" 40#include "RenderBoxModelObject.h" 41#include "RenderText.h" 42#include "ScopedEventQueue.h" 43#include "TextIterator.h" 44#include "VisiblePosition.h" 45#include "VisibleUnits.h" 46#include "htmlediting.h" 47#include "markup.h" 48#include <stdio.h> 49#include <wtf/RefCountedLeakCounter.h> 50#include <wtf/text/CString.h> 51#include <wtf/text/StringBuilder.h> 52 53#if PLATFORM(IOS) 54#include "SelectionRect.h" 55#endif 56 57namespace WebCore { 58 59using namespace HTMLNames; 60 61DEFINE_DEBUG_ONLY_GLOBAL(WTF::RefCountedLeakCounter, rangeCounter, ("Range")); 62 63inline Range::Range(Document& ownerDocument) 64 : m_ownerDocument(ownerDocument) 65 , m_start(&ownerDocument) 66 , m_end(&ownerDocument) 67{ 68#ifndef NDEBUG 69 rangeCounter.increment(); 70#endif 71 72 m_ownerDocument->attachRange(this); 73} 74 75PassRefPtr<Range> Range::create(Document& ownerDocument) 76{ 77 return adoptRef(new Range(ownerDocument)); 78} 79 80inline Range::Range(Document& ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset) 81 : m_ownerDocument(ownerDocument) 82 , m_start(&ownerDocument) 83 , m_end(&ownerDocument) 84{ 85#ifndef NDEBUG 86 rangeCounter.increment(); 87#endif 88 89 m_ownerDocument->attachRange(this); 90 91 // Simply setting the containers and offsets directly would not do any of the checking 92 // that setStart and setEnd do, so we call those functions. 93 setStart(startContainer, startOffset); 94 setEnd(endContainer, endOffset); 95} 96 97PassRefPtr<Range> Range::create(Document& ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset) 98{ 99 return adoptRef(new Range(ownerDocument, startContainer, startOffset, endContainer, endOffset)); 100} 101 102PassRefPtr<Range> Range::create(Document& ownerDocument, const Position& start, const Position& end) 103{ 104 return adoptRef(new Range(ownerDocument, start.containerNode(), start.computeOffsetInContainerNode(), end.containerNode(), end.computeOffsetInContainerNode())); 105} 106 107PassRefPtr<Range> Range::create(ScriptExecutionContext& context) 108{ 109 return adoptRef(new Range(toDocument(context))); 110} 111 112#if PLATFORM(IOS) 113PassRefPtr<Range> Range::create(Document& ownerDocument, const VisiblePosition& visibleStart, const VisiblePosition& visibleEnd) 114{ 115 Position start = visibleStart.deepEquivalent().parentAnchoredEquivalent(); 116 Position end = visibleEnd.deepEquivalent().parentAnchoredEquivalent(); 117 return adoptRef(new Range(ownerDocument, start.anchorNode(), start.deprecatedEditingOffset(), end.anchorNode(), end.deprecatedEditingOffset())); 118} 119#endif 120 121Range::~Range() 122{ 123 // Always detach (even if we've already detached) to fix https://bugs.webkit.org/show_bug.cgi?id=26044 124 m_ownerDocument->detachRange(this); 125 126#ifndef NDEBUG 127 rangeCounter.decrement(); 128#endif 129} 130 131void Range::setDocument(Document& document) 132{ 133 ASSERT(&m_ownerDocument.get() != &document); 134 m_ownerDocument->detachRange(this); 135 m_ownerDocument = document; 136 m_start.setToStartOfNode(&document); 137 m_end.setToStartOfNode(&document); 138 m_ownerDocument->attachRange(this); 139} 140 141Node* Range::startContainer(ExceptionCode& ec) const 142{ 143 if (!m_start.container()) { 144 ec = INVALID_STATE_ERR; 145 return 0; 146 } 147 148 return m_start.container(); 149} 150 151int Range::startOffset(ExceptionCode& ec) const 152{ 153 if (!m_start.container()) { 154 ec = INVALID_STATE_ERR; 155 return 0; 156 } 157 158 return m_start.offset(); 159} 160 161Node* Range::endContainer(ExceptionCode& ec) const 162{ 163 if (!m_start.container()) { 164 ec = INVALID_STATE_ERR; 165 return 0; 166 } 167 168 return m_end.container(); 169} 170 171int Range::endOffset(ExceptionCode& ec) const 172{ 173 if (!m_start.container()) { 174 ec = INVALID_STATE_ERR; 175 return 0; 176 } 177 178 return m_end.offset(); 179} 180 181Node* Range::commonAncestorContainer(ExceptionCode& ec) const 182{ 183 if (!m_start.container()) { 184 ec = INVALID_STATE_ERR; 185 return 0; 186 } 187 188 return commonAncestorContainer(m_start.container(), m_end.container()); 189} 190 191Node* Range::commonAncestorContainer(Node* containerA, Node* containerB) 192{ 193 for (Node* parentA = containerA; parentA; parentA = parentA->parentNode()) { 194 for (Node* parentB = containerB; parentB; parentB = parentB->parentNode()) { 195 if (parentA == parentB) 196 return parentA; 197 } 198 } 199 return 0; 200} 201 202bool Range::collapsed(ExceptionCode& ec) const 203{ 204 if (!m_start.container()) { 205 ec = INVALID_STATE_ERR; 206 return 0; 207 } 208 209 return m_start == m_end; 210} 211 212static inline bool checkForDifferentRootContainer(const RangeBoundaryPoint& start, const RangeBoundaryPoint& end) 213{ 214 Node* endRootContainer = end.container(); 215 while (endRootContainer->parentNode()) 216 endRootContainer = endRootContainer->parentNode(); 217 Node* startRootContainer = start.container(); 218 while (startRootContainer->parentNode()) 219 startRootContainer = startRootContainer->parentNode(); 220 221 return startRootContainer != endRootContainer || (Range::compareBoundaryPoints(start, end, ASSERT_NO_EXCEPTION) > 0); 222} 223 224void Range::setStart(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec) 225{ 226 if (!m_start.container()) { 227 ec = INVALID_STATE_ERR; 228 return; 229 } 230 231 if (!refNode) { 232 ec = NOT_FOUND_ERR; 233 return; 234 } 235 236 bool didMoveDocument = false; 237 if (&refNode->document() != &ownerDocument()) { 238 setDocument(refNode->document()); 239 didMoveDocument = true; 240 } 241 242 ec = 0; 243 Node* childNode = checkNodeWOffset(refNode.get(), offset, ec); 244 if (ec) 245 return; 246 247 m_start.set(refNode, offset, childNode); 248 249 if (didMoveDocument || checkForDifferentRootContainer(m_start, m_end)) 250 collapse(true, ec); 251} 252 253void Range::setEnd(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec) 254{ 255 if (!m_start.container()) { 256 ec = INVALID_STATE_ERR; 257 return; 258 } 259 260 if (!refNode) { 261 ec = NOT_FOUND_ERR; 262 return; 263 } 264 265 bool didMoveDocument = false; 266 if (&refNode->document() != &ownerDocument()) { 267 setDocument(refNode->document()); 268 didMoveDocument = true; 269 } 270 271 ec = 0; 272 Node* childNode = checkNodeWOffset(refNode.get(), offset, ec); 273 if (ec) 274 return; 275 276 m_end.set(refNode, offset, childNode); 277 278 if (didMoveDocument || checkForDifferentRootContainer(m_start, m_end)) 279 collapse(false, ec); 280} 281 282void Range::setStart(const Position& start, ExceptionCode& ec) 283{ 284 Position parentAnchored = start.parentAnchoredEquivalent(); 285 setStart(parentAnchored.containerNode(), parentAnchored.offsetInContainerNode(), ec); 286} 287 288void Range::setEnd(const Position& end, ExceptionCode& ec) 289{ 290 Position parentAnchored = end.parentAnchoredEquivalent(); 291 setEnd(parentAnchored.containerNode(), parentAnchored.offsetInContainerNode(), ec); 292} 293 294void Range::collapse(bool toStart, ExceptionCode& ec) 295{ 296 if (!m_start.container()) { 297 ec = INVALID_STATE_ERR; 298 return; 299 } 300 301 if (toStart) 302 m_end = m_start; 303 else 304 m_start = m_end; 305} 306 307bool Range::isPointInRange(Node* refNode, int offset, ExceptionCode& ec) 308{ 309 if (!m_start.container()) { 310 ec = INVALID_STATE_ERR; 311 return false; 312 } 313 314 if (!refNode) { 315 ec = HIERARCHY_REQUEST_ERR; 316 return false; 317 } 318 319 if (!refNode->inDocument() || &refNode->document() != &ownerDocument()) { 320 return false; 321 } 322 323 ec = 0; 324 checkNodeWOffset(refNode, offset, ec); 325 if (ec) 326 return false; 327 328 return compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset(), ec) >= 0 && !ec 329 && compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset(), ec) <= 0 && !ec; 330} 331 332short Range::comparePoint(Node* refNode, int offset, ExceptionCode& ec) const 333{ 334 // http://developer.mozilla.org/en/docs/DOM:range.comparePoint 335 // This method returns -1, 0 or 1 depending on if the point described by the 336 // refNode node and an offset within the node is before, same as, or after the range respectively. 337 338 if (!m_start.container()) { 339 ec = INVALID_STATE_ERR; 340 return 0; 341 } 342 343 if (!refNode) { 344 ec = HIERARCHY_REQUEST_ERR; 345 return 0; 346 } 347 348 if (!refNode->inDocument() || &refNode->document() != &ownerDocument()) { 349 ec = WRONG_DOCUMENT_ERR; 350 return 0; 351 } 352 353 ec = 0; 354 checkNodeWOffset(refNode, offset, ec); 355 if (ec) 356 return 0; 357 358 // compare to start, and point comes before 359 if (compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset(), ec) < 0) 360 return -1; 361 362 if (ec) 363 return 0; 364 365 // compare to end, and point comes after 366 if (compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset(), ec) > 0 && !ec) 367 return 1; 368 369 // point is in the middle of this range, or on the boundary points 370 return 0; 371} 372 373Range::CompareResults Range::compareNode(Node* refNode, ExceptionCode& ec) const 374{ 375 // http://developer.mozilla.org/en/docs/DOM:range.compareNode 376 // This method returns 0, 1, 2, or 3 based on if the node is before, after, 377 // before and after(surrounds), or inside the range, respectively 378 379 if (!refNode) { 380 ec = NOT_FOUND_ERR; 381 return NODE_BEFORE; 382 } 383 384 if (!m_start.container() && refNode->inDocument()) { 385 ec = INVALID_STATE_ERR; 386 return NODE_BEFORE; 387 } 388 389 if (m_start.container() && !refNode->inDocument()) { 390 // Firefox doesn't throw an exception for this case; it returns 0. 391 return NODE_BEFORE; 392 } 393 394 if (&refNode->document() != &ownerDocument()) { 395 // Firefox doesn't throw an exception for this case; it returns 0. 396 return NODE_BEFORE; 397 } 398 399 ContainerNode* parentNode = refNode->parentNode(); 400 int nodeIndex = refNode->nodeIndex(); 401 402 if (!parentNode) { 403 // if the node is the top document we should return NODE_BEFORE_AND_AFTER 404 // but we throw to match firefox behavior 405 ec = NOT_FOUND_ERR; 406 return NODE_BEFORE; 407 } 408 409 if (comparePoint(parentNode, nodeIndex, ec) < 0) { // starts before 410 if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range 411 return NODE_BEFORE_AND_AFTER; 412 return NODE_BEFORE; // ends before or in the range 413 } else { // starts at or after the range start 414 if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range 415 return NODE_AFTER; 416 return NODE_INSIDE; // ends inside the range 417 } 418} 419 420short Range::compareBoundaryPoints(CompareHow how, const Range* sourceRange, ExceptionCode& ec) const 421{ 422 if (!m_start.container()) { 423 ec = INVALID_STATE_ERR; 424 return 0; 425 } 426 427 if (!sourceRange) { 428 ec = NOT_FOUND_ERR; 429 return 0; 430 } 431 432 ec = 0; 433 Node* thisCont = commonAncestorContainer(ec); 434 if (ec) 435 return 0; 436 Node* sourceCont = sourceRange->commonAncestorContainer(ec); 437 if (ec) 438 return 0; 439 440 if (&thisCont->document() != &sourceCont->document()) { 441 ec = WRONG_DOCUMENT_ERR; 442 return 0; 443 } 444 445 Node* thisTop = thisCont; 446 Node* sourceTop = sourceCont; 447 while (thisTop->parentNode()) 448 thisTop = thisTop->parentNode(); 449 while (sourceTop->parentNode()) 450 sourceTop = sourceTop->parentNode(); 451 if (thisTop != sourceTop) { // in different DocumentFragments 452 ec = WRONG_DOCUMENT_ERR; 453 return 0; 454 } 455 456 switch (how) { 457 case START_TO_START: 458 return compareBoundaryPoints(m_start, sourceRange->m_start, ec); 459 case START_TO_END: 460 return compareBoundaryPoints(m_end, sourceRange->m_start, ec); 461 case END_TO_END: 462 return compareBoundaryPoints(m_end, sourceRange->m_end, ec); 463 case END_TO_START: 464 return compareBoundaryPoints(m_start, sourceRange->m_end, ec); 465 } 466 467 ec = SYNTAX_ERR; 468 return 0; 469} 470 471short Range::compareBoundaryPoints(Node* containerA, int offsetA, Node* containerB, int offsetB, ExceptionCode& ec) 472{ 473 ASSERT(containerA); 474 ASSERT(containerB); 475 476 if (!containerA) 477 return -1; 478 if (!containerB) 479 return 1; 480 481 // see DOM2 traversal & range section 2.5 482 483 // case 1: both points have the same container 484 if (containerA == containerB) { 485 if (offsetA == offsetB) 486 return 0; // A is equal to B 487 if (offsetA < offsetB) 488 return -1; // A is before B 489 else 490 return 1; // A is after B 491 } 492 493 // case 2: node C (container B or an ancestor) is a child node of A 494 Node* c = containerB; 495 while (c && c->parentNode() != containerA) 496 c = c->parentNode(); 497 if (c) { 498 int offsetC = 0; 499 Node* n = containerA->firstChild(); 500 while (n != c && offsetC < offsetA) { 501 offsetC++; 502 n = n->nextSibling(); 503 } 504 505 if (offsetA <= offsetC) 506 return -1; // A is before B 507 else 508 return 1; // A is after B 509 } 510 511 // case 3: node C (container A or an ancestor) is a child node of B 512 c = containerA; 513 while (c && c->parentNode() != containerB) 514 c = c->parentNode(); 515 if (c) { 516 int offsetC = 0; 517 Node* n = containerB->firstChild(); 518 while (n != c && offsetC < offsetB) { 519 offsetC++; 520 n = n->nextSibling(); 521 } 522 523 if (offsetC < offsetB) 524 return -1; // A is before B 525 else 526 return 1; // A is after B 527 } 528 529 // case 4: containers A & B are siblings, or children of siblings 530 // ### we need to do a traversal here instead 531 Node* commonAncestor = commonAncestorContainer(containerA, containerB); 532 if (!commonAncestor) { 533 ec = WRONG_DOCUMENT_ERR; 534 return 0; 535 } 536 Node* childA = containerA; 537 while (childA && childA->parentNode() != commonAncestor) 538 childA = childA->parentNode(); 539 if (!childA) 540 childA = commonAncestor; 541 Node* childB = containerB; 542 while (childB && childB->parentNode() != commonAncestor) 543 childB = childB->parentNode(); 544 if (!childB) 545 childB = commonAncestor; 546 547 if (childA == childB) 548 return 0; // A is equal to B 549 550 Node* n = commonAncestor->firstChild(); 551 while (n) { 552 if (n == childA) 553 return -1; // A is before B 554 if (n == childB) 555 return 1; // A is after B 556 n = n->nextSibling(); 557 } 558 559 // Should never reach this point. 560 ASSERT_NOT_REACHED(); 561 return 0; 562} 563 564short Range::compareBoundaryPoints(const RangeBoundaryPoint& boundaryA, const RangeBoundaryPoint& boundaryB, ExceptionCode& ec) 565{ 566 return compareBoundaryPoints(boundaryA.container(), boundaryA.offset(), boundaryB.container(), boundaryB.offset(), ec); 567} 568 569bool Range::boundaryPointsValid() const 570{ 571 ExceptionCode ec = 0; 572 return m_start.container() && compareBoundaryPoints(m_start, m_end, ec) <= 0 && !ec; 573} 574 575void Range::deleteContents(ExceptionCode& ec) 576{ 577 checkDeleteExtract(ec); 578 if (ec) 579 return; 580 581 processContents(Delete, ec); 582} 583 584bool Range::intersectsNode(Node* refNode, ExceptionCode& ec) 585{ 586 // http://developer.mozilla.org/en/docs/DOM:range.intersectsNode 587 // Returns a bool if the node intersects the range. 588 589 // Throw exception if the range is already detached. 590 if (!m_start.container()) { 591 ec = INVALID_STATE_ERR; 592 return false; 593 } 594 if (!refNode) { 595 ec = NOT_FOUND_ERR; 596 return false; 597 } 598 599 if (!refNode->inDocument() || &refNode->document() != &ownerDocument()) { 600 // Firefox doesn't throw an exception for these cases; it returns false. 601 return false; 602 } 603 604 ContainerNode* parentNode = refNode->parentNode(); 605 int nodeIndex = refNode->nodeIndex(); 606 607 if (!parentNode) { 608 // if the node is the top document we should return NODE_BEFORE_AND_AFTER 609 // but we throw to match firefox behavior 610 ec = NOT_FOUND_ERR; 611 return false; 612 } 613 614 if (comparePoint(parentNode, nodeIndex, ec) < 0 && // starts before start 615 comparePoint(parentNode, nodeIndex + 1, ec) < 0) { // ends before start 616 return false; 617 } else if (comparePoint(parentNode, nodeIndex, ec) > 0 && // starts after end 618 comparePoint(parentNode, nodeIndex + 1, ec) > 0) { // ends after end 619 return false; 620 } 621 622 return true; // all other cases 623} 624 625static inline Node* highestAncestorUnderCommonRoot(Node* node, Node* commonRoot) 626{ 627 if (node == commonRoot) 628 return 0; 629 630 ASSERT(commonRoot->contains(node)); 631 632 while (node->parentNode() != commonRoot) 633 node = node->parentNode(); 634 635 return node; 636} 637 638static inline Node* childOfCommonRootBeforeOffset(Node* container, unsigned offset, Node* commonRoot) 639{ 640 ASSERT(container); 641 ASSERT(commonRoot); 642 643 if (!commonRoot->contains(container)) 644 return 0; 645 646 if (container == commonRoot) { 647 container = container->firstChild(); 648 for (unsigned i = 0; container && i < offset; i++) 649 container = container->nextSibling(); 650 } else { 651 while (container->parentNode() != commonRoot) 652 container = container->parentNode(); 653 } 654 655 return container; 656} 657 658static inline unsigned lengthOfContentsInNode(Node* node) 659{ 660 // This switch statement must be consistent with that of Range::processContentsBetweenOffsets. 661 switch (node->nodeType()) { 662 case Node::TEXT_NODE: 663 case Node::CDATA_SECTION_NODE: 664 case Node::COMMENT_NODE: 665 return toCharacterData(node)->length(); 666 case Node::PROCESSING_INSTRUCTION_NODE: 667 return toProcessingInstruction(node)->data().length(); 668 case Node::ELEMENT_NODE: 669 case Node::ATTRIBUTE_NODE: 670 case Node::ENTITY_REFERENCE_NODE: 671 case Node::ENTITY_NODE: 672 case Node::DOCUMENT_NODE: 673 case Node::DOCUMENT_TYPE_NODE: 674 case Node::DOCUMENT_FRAGMENT_NODE: 675 case Node::NOTATION_NODE: 676 case Node::XPATH_NAMESPACE_NODE: 677 return node->childNodeCount(); 678 } 679 ASSERT_NOT_REACHED(); 680 return 0; 681} 682 683PassRefPtr<DocumentFragment> Range::processContents(ActionType action, ExceptionCode& ec) 684{ 685 typedef Vector<RefPtr<Node>> NodeVector; 686 687 RefPtr<DocumentFragment> fragment; 688 if (action == Extract || action == Clone) 689 fragment = DocumentFragment::create(ownerDocument()); 690 691 ec = 0; 692 if (collapsed(ec)) 693 return fragment.release(); 694 if (ec) 695 return 0; 696 697 RefPtr<Node> commonRoot = commonAncestorContainer(ec); 698 if (ec) 699 return 0; 700 ASSERT(commonRoot); 701 702 if (m_start.container() == m_end.container()) { 703 processContentsBetweenOffsets(action, fragment, m_start.container(), m_start.offset(), m_end.offset(), ec); 704 return fragment; 705 } 706 707 // Since mutation events can modify the range during the process, the boundary points need to be saved. 708 RangeBoundaryPoint originalStart(m_start); 709 RangeBoundaryPoint originalEnd(m_end); 710 711 // what is the highest node that partially selects the start / end of the range? 712 RefPtr<Node> partialStart = highestAncestorUnderCommonRoot(originalStart.container(), commonRoot.get()); 713 RefPtr<Node> partialEnd = highestAncestorUnderCommonRoot(originalEnd.container(), commonRoot.get()); 714 715 // Start and end containers are different. 716 // There are three possibilities here: 717 // 1. Start container == commonRoot (End container must be a descendant) 718 // 2. End container == commonRoot (Start container must be a descendant) 719 // 3. Neither is commonRoot, they are both descendants 720 // 721 // In case 3, we grab everything after the start (up until a direct child 722 // of commonRoot) into leftContents, and everything before the end (up until 723 // a direct child of commonRoot) into rightContents. Then we process all 724 // commonRoot children between leftContents and rightContents 725 // 726 // In case 1 or 2, we skip either processing of leftContents or rightContents, 727 // in which case the last lot of nodes either goes from the first or last 728 // child of commonRoot. 729 // 730 // These are deleted, cloned, or extracted (i.e. both) depending on action. 731 732 // Note that we are verifying that our common root hierarchy is still intact 733 // after any DOM mutation event, at various stages below. See webkit bug 60350. 734 735 RefPtr<Node> leftContents; 736 if (originalStart.container() != commonRoot && commonRoot->contains(originalStart.container())) { 737 leftContents = processContentsBetweenOffsets(action, 0, originalStart.container(), originalStart.offset(), lengthOfContentsInNode(originalStart.container()), ec); 738 leftContents = processAncestorsAndTheirSiblings(action, originalStart.container(), ProcessContentsForward, leftContents, commonRoot.get(), ec); 739 } 740 741 RefPtr<Node> rightContents; 742 if (m_end.container() != commonRoot && commonRoot->contains(originalEnd.container())) { 743 rightContents = processContentsBetweenOffsets(action, 0, originalEnd.container(), 0, originalEnd.offset(), ec); 744 rightContents = processAncestorsAndTheirSiblings(action, originalEnd.container(), ProcessContentsBackward, rightContents, commonRoot.get(), ec); 745 } 746 747 // delete all children of commonRoot between the start and end container 748 RefPtr<Node> processStart = childOfCommonRootBeforeOffset(originalStart.container(), originalStart.offset(), commonRoot.get()); 749 if (processStart && originalStart.container() != commonRoot) // processStart contains nodes before m_start. 750 processStart = processStart->nextSibling(); 751 RefPtr<Node> processEnd = childOfCommonRootBeforeOffset(originalEnd.container(), originalEnd.offset(), commonRoot.get()); 752 753 // Collapse the range, making sure that the result is not within a node that was partially selected. 754 if (action == Extract || action == Delete) { 755 if (partialStart && commonRoot->contains(partialStart.get())) 756 setStart(partialStart->parentNode(), partialStart->nodeIndex() + 1, ec); 757 else if (partialEnd && commonRoot->contains(partialEnd.get())) 758 setStart(partialEnd->parentNode(), partialEnd->nodeIndex(), ec); 759 if (ec) 760 return 0; 761 m_end = m_start; 762 } 763 764 // Now add leftContents, stuff in between, and rightContents to the fragment 765 // (or just delete the stuff in between) 766 767 if ((action == Extract || action == Clone) && leftContents) 768 fragment->appendChild(leftContents, ec); 769 770 if (processStart) { 771 NodeVector nodes; 772 for (Node* n = processStart.get(); n && n != processEnd; n = n->nextSibling()) 773 nodes.append(n); 774 processNodes(action, nodes, commonRoot, fragment, ec); 775 } 776 777 if ((action == Extract || action == Clone) && rightContents) 778 fragment->appendChild(rightContents, ec); 779 780 return fragment.release(); 781} 782 783static inline void deleteCharacterData(PassRefPtr<CharacterData> data, unsigned startOffset, unsigned endOffset, ExceptionCode& ec) 784{ 785 if (data->length() - endOffset) 786 data->deleteData(endOffset, data->length() - endOffset, ec); 787 if (startOffset) 788 data->deleteData(0, startOffset, ec); 789} 790 791PassRefPtr<Node> Range::processContentsBetweenOffsets(ActionType action, PassRefPtr<DocumentFragment> fragment, Node* container, unsigned startOffset, unsigned endOffset, ExceptionCode& ec) 792{ 793 ASSERT(container); 794 ASSERT(startOffset <= endOffset); 795 796 // This switch statement must be consistent with that of lengthOfContentsInNode. 797 RefPtr<Node> result; 798 switch (container->nodeType()) { 799 case Node::TEXT_NODE: 800 case Node::CDATA_SECTION_NODE: 801 case Node::COMMENT_NODE: 802 endOffset = std::min(endOffset, static_cast<CharacterData*>(container)->length()); 803 startOffset = std::min(startOffset, endOffset); 804 if (action == Extract || action == Clone) { 805 RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(container->cloneNode(true)); 806 deleteCharacterData(c, startOffset, endOffset, ec); 807 if (fragment) { 808 result = fragment; 809 result->appendChild(c.release(), ec); 810 } else 811 result = c.release(); 812 } 813 if (action == Extract || action == Delete) 814 toCharacterData(container)->deleteData(startOffset, endOffset - startOffset, ec); 815 break; 816 case Node::PROCESSING_INSTRUCTION_NODE: 817 endOffset = std::min(endOffset, static_cast<ProcessingInstruction*>(container)->data().length()); 818 startOffset = std::min(startOffset, endOffset); 819 if (action == Extract || action == Clone) { 820 RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(container->cloneNode(true)); 821 c->setData(c->data().substring(startOffset, endOffset - startOffset), ec); 822 if (fragment) { 823 result = fragment; 824 result->appendChild(c.release(), ec); 825 } else 826 result = c.release(); 827 } 828 if (action == Extract || action == Delete) { 829 ProcessingInstruction* pi = toProcessingInstruction(container); 830 String data(pi->data()); 831 data.remove(startOffset, endOffset - startOffset); 832 pi->setData(data, ec); 833 } 834 break; 835 case Node::ELEMENT_NODE: 836 case Node::ATTRIBUTE_NODE: 837 case Node::ENTITY_REFERENCE_NODE: 838 case Node::ENTITY_NODE: 839 case Node::DOCUMENT_NODE: 840 case Node::DOCUMENT_TYPE_NODE: 841 case Node::DOCUMENT_FRAGMENT_NODE: 842 case Node::NOTATION_NODE: 843 case Node::XPATH_NAMESPACE_NODE: 844 // FIXME: Should we assert that some nodes never appear here? 845 if (action == Extract || action == Clone) { 846 if (fragment) 847 result = fragment; 848 else 849 result = container->cloneNode(false); 850 } 851 852 Node* n = container->firstChild(); 853 Vector<RefPtr<Node>> nodes; 854 for (unsigned i = startOffset; n && i; i--) 855 n = n->nextSibling(); 856 for (unsigned i = startOffset; n && i < endOffset; i++, n = n->nextSibling()) 857 nodes.append(n); 858 859 processNodes(action, nodes, container, result, ec); 860 break; 861 } 862 863 return result.release(); 864} 865 866void Range::processNodes(ActionType action, Vector<RefPtr<Node>>& nodes, PassRefPtr<Node> oldContainer, PassRefPtr<Node> newContainer, ExceptionCode& ec) 867{ 868 for (unsigned i = 0; i < nodes.size(); i++) { 869 switch (action) { 870 case Delete: 871 oldContainer->removeChild(nodes[i].get(), ec); 872 break; 873 case Extract: 874 newContainer->appendChild(nodes[i].release(), ec); // will remove n from its parent 875 break; 876 case Clone: 877 newContainer->appendChild(nodes[i]->cloneNode(true), ec); 878 break; 879 } 880 } 881} 882 883PassRefPtr<Node> Range::processAncestorsAndTheirSiblings(ActionType action, Node* container, ContentsProcessDirection direction, PassRefPtr<Node> passedClonedContainer, Node* commonRoot, ExceptionCode& ec) 884{ 885 typedef Vector<RefPtr<Node>> NodeVector; 886 887 RefPtr<Node> clonedContainer = passedClonedContainer; 888 Vector<RefPtr<Node>> ancestors; 889 for (ContainerNode* n = container->parentNode(); n && n != commonRoot; n = n->parentNode()) 890 ancestors.append(n); 891 892 RefPtr<Node> firstChildInAncestorToProcess = direction == ProcessContentsForward ? container->nextSibling() : container->previousSibling(); 893 for (Vector<RefPtr<Node>>::const_iterator it = ancestors.begin(); it != ancestors.end(); ++it) { 894 RefPtr<Node> ancestor = *it; 895 if (action == Extract || action == Clone) { 896 if (RefPtr<Node> clonedAncestor = ancestor->cloneNode(false)) { // Might have been removed already during mutation event. 897 clonedAncestor->appendChild(clonedContainer, ec); 898 clonedContainer = clonedAncestor; 899 } 900 } 901 902 // Copy siblings of an ancestor of start/end containers 903 // FIXME: This assertion may fail if DOM is modified during mutation event 904 // FIXME: Share code with Range::processNodes 905 ASSERT(!firstChildInAncestorToProcess || firstChildInAncestorToProcess->parentNode() == ancestor); 906 907 NodeVector nodes; 908 for (Node* child = firstChildInAncestorToProcess.get(); child; 909 child = (direction == ProcessContentsForward) ? child->nextSibling() : child->previousSibling()) 910 nodes.append(child); 911 912 for (NodeVector::const_iterator it = nodes.begin(); it != nodes.end(); ++it) { 913 Node* child = it->get(); 914 switch (action) { 915 case Delete: 916 ancestor->removeChild(child, ec); 917 break; 918 case Extract: // will remove child from ancestor 919 if (direction == ProcessContentsForward) 920 clonedContainer->appendChild(child, ec); 921 else 922 clonedContainer->insertBefore(child, clonedContainer->firstChild(), ec); 923 break; 924 case Clone: 925 if (direction == ProcessContentsForward) 926 clonedContainer->appendChild(child->cloneNode(true), ec); 927 else 928 clonedContainer->insertBefore(child->cloneNode(true), clonedContainer->firstChild(), ec); 929 break; 930 } 931 } 932 firstChildInAncestorToProcess = direction == ProcessContentsForward ? ancestor->nextSibling() : ancestor->previousSibling(); 933 } 934 935 return clonedContainer.release(); 936} 937 938PassRefPtr<DocumentFragment> Range::extractContents(ExceptionCode& ec) 939{ 940 checkDeleteExtract(ec); 941 if (ec) 942 return 0; 943 944 return processContents(Extract, ec); 945} 946 947PassRefPtr<DocumentFragment> Range::cloneContents(ExceptionCode& ec) 948{ 949 if (!m_start.container()) { 950 ec = INVALID_STATE_ERR; 951 return 0; 952 } 953 954 return processContents(Clone, ec); 955} 956 957void Range::insertNode(PassRefPtr<Node> prpNewNode, ExceptionCode& ec) 958{ 959 RefPtr<Node> newNode = prpNewNode; 960 961 ec = 0; 962 963 if (!m_start.container()) { 964 ec = INVALID_STATE_ERR; 965 return; 966 } 967 968 if (!newNode) { 969 ec = NOT_FOUND_ERR; 970 return; 971 } 972 973 // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of 974 // the Range is read-only. 975 if (containedByReadOnly()) { 976 ec = NO_MODIFICATION_ALLOWED_ERR; 977 return; 978 } 979 980 // HIERARCHY_REQUEST_ERR: Raised if the container of the start of the Range is of a type that 981 // does not allow children of the type of newNode or if newNode is an ancestor of the container. 982 983 // an extra one here - if a text node is going to split, it must have a parent to insert into 984 bool startIsText = m_start.container()->isTextNode(); 985 if (startIsText && !m_start.container()->parentNode()) { 986 ec = HIERARCHY_REQUEST_ERR; 987 return; 988 } 989 990 // In the case where the container is a text node, we check against the container's parent, because 991 // text nodes get split up upon insertion. 992 Node* checkAgainst; 993 if (startIsText) 994 checkAgainst = m_start.container()->parentNode(); 995 else 996 checkAgainst = m_start.container(); 997 998 Node::NodeType newNodeType = newNode->nodeType(); 999 int numNewChildren; 1000 if (newNodeType == Node::DOCUMENT_FRAGMENT_NODE && !newNode->isShadowRoot()) { 1001 // check each child node, not the DocumentFragment itself 1002 numNewChildren = 0; 1003 for (Node* c = newNode->firstChild(); c; c = c->nextSibling()) { 1004 if (!checkAgainst->childTypeAllowed(c->nodeType())) { 1005 ec = HIERARCHY_REQUEST_ERR; 1006 return; 1007 } 1008 ++numNewChildren; 1009 } 1010 } else { 1011 numNewChildren = 1; 1012 if (!checkAgainst->childTypeAllowed(newNodeType)) { 1013 ec = HIERARCHY_REQUEST_ERR; 1014 return; 1015 } 1016 } 1017 1018 for (Node* n = m_start.container(); n; n = n->parentNode()) { 1019 if (n == newNode) { 1020 ec = HIERARCHY_REQUEST_ERR; 1021 return; 1022 } 1023 } 1024 1025 // INVALID_NODE_TYPE_ERR: Raised if newNode is an Attr, Entity, Notation, ShadowRoot or Document node. 1026 switch (newNodeType) { 1027 case Node::ATTRIBUTE_NODE: 1028 case Node::ENTITY_NODE: 1029 case Node::NOTATION_NODE: 1030 case Node::DOCUMENT_NODE: 1031 ec = RangeException::INVALID_NODE_TYPE_ERR; 1032 return; 1033 default: 1034 if (newNode->isShadowRoot()) { 1035 ec = RangeException::INVALID_NODE_TYPE_ERR; 1036 return; 1037 } 1038 break; 1039 } 1040 1041 EventQueueScope scope; 1042 bool collapsed = m_start == m_end; 1043 RefPtr<Node> container; 1044 if (startIsText) { 1045 container = m_start.container(); 1046 RefPtr<Text> newText = toText(container.get())->splitText(m_start.offset(), ec); 1047 if (ec) 1048 return; 1049 1050 container = m_start.container(); 1051 container->parentNode()->insertBefore(newNode.release(), newText.get(), ec); 1052 if (ec) 1053 return; 1054 1055 if (collapsed && newText->parentNode() == container && &container->document() == &ownerDocument()) 1056 m_end.setToBeforeChild(newText.get()); 1057 } else { 1058 container = m_start.container(); 1059 RefPtr<Node> firstInsertedChild = newNodeType == Node::DOCUMENT_FRAGMENT_NODE ? newNode->firstChild() : newNode; 1060 RefPtr<Node> lastInsertedChild = newNodeType == Node::DOCUMENT_FRAGMENT_NODE ? newNode->lastChild() : newNode; 1061 RefPtr<Node> childAfterInsertedContent = container->childNode(m_start.offset()); 1062 container->insertBefore(newNode.release(), childAfterInsertedContent.get(), ec); 1063 if (ec) 1064 return; 1065 1066 if (collapsed && numNewChildren && &container->document() == &ownerDocument()) { 1067 if (firstInsertedChild->parentNode() == container) 1068 m_start.setToBeforeChild(firstInsertedChild.get()); 1069 if (lastInsertedChild->parentNode() == container) 1070 m_end.set(container, lastInsertedChild->nodeIndex() + 1, lastInsertedChild.get()); 1071 } 1072 } 1073} 1074 1075String Range::toString(ExceptionCode& ec) const 1076{ 1077 if (!m_start.container()) { 1078 ec = INVALID_STATE_ERR; 1079 return String(); 1080 } 1081 1082 StringBuilder builder; 1083 1084 Node* pastLast = pastLastNode(); 1085 for (Node* n = firstNode(); n != pastLast; n = NodeTraversal::next(n)) { 1086 if (n->nodeType() == Node::TEXT_NODE || n->nodeType() == Node::CDATA_SECTION_NODE) { 1087 const String& data = static_cast<CharacterData*>(n)->data(); 1088 int length = data.length(); 1089 int start = (n == m_start.container()) ? std::min(std::max(0, m_start.offset()), length) : 0; 1090 int end = (n == m_end.container()) ? std::min(std::max(start, m_end.offset()), length) : length; 1091 builder.append(data, start, end - start); 1092 } 1093 } 1094 1095 return builder.toString(); 1096} 1097 1098String Range::toHTML() const 1099{ 1100 return createMarkup(*this); 1101} 1102 1103String Range::text() const 1104{ 1105 if (!m_start.container()) 1106 return String(); 1107 1108 // We need to update layout, since plainText uses line boxes in the render tree. 1109 // FIXME: As with innerText, we'd like this to work even if there are no render objects. 1110 m_start.container()->document().updateLayout(); 1111 1112 return plainText(this); 1113} 1114 1115PassRefPtr<DocumentFragment> Range::createContextualFragment(const String& markup, ExceptionCode& ec) 1116{ 1117 if (!m_start.container()) { 1118 ec = INVALID_STATE_ERR; 1119 return 0; 1120 } 1121 1122 Node* element = m_start.container()->isElementNode() ? m_start.container() : m_start.container()->parentNode(); 1123 if (!element || !element->isHTMLElement()) { 1124 ec = NOT_SUPPORTED_ERR; 1125 return 0; 1126 } 1127 1128 RefPtr<DocumentFragment> fragment = WebCore::createContextualFragment(markup, toHTMLElement(element), AllowScriptingContentAndDoNotMarkAlreadyStarted, ec); 1129 if (!fragment) 1130 return 0; 1131 1132 return fragment.release(); 1133} 1134 1135 1136void Range::detach(ExceptionCode& ec) 1137{ 1138 // Check first to see if we've already detached: 1139 if (!m_start.container()) { 1140 ec = INVALID_STATE_ERR; 1141 return; 1142 } 1143 1144 m_ownerDocument->detachRange(this); 1145 1146 m_start.clear(); 1147 m_end.clear(); 1148} 1149 1150Node* Range::checkNodeWOffset(Node* n, int offset, ExceptionCode& ec) const 1151{ 1152 switch (n->nodeType()) { 1153 case Node::DOCUMENT_TYPE_NODE: 1154 case Node::ENTITY_NODE: 1155 case Node::NOTATION_NODE: 1156 ec = RangeException::INVALID_NODE_TYPE_ERR; 1157 return 0; 1158 case Node::CDATA_SECTION_NODE: 1159 case Node::COMMENT_NODE: 1160 case Node::TEXT_NODE: 1161 if (static_cast<unsigned>(offset) > toCharacterData(n)->length()) 1162 ec = INDEX_SIZE_ERR; 1163 return 0; 1164 case Node::PROCESSING_INSTRUCTION_NODE: 1165 if (static_cast<unsigned>(offset) > toProcessingInstruction(n)->data().length()) 1166 ec = INDEX_SIZE_ERR; 1167 return 0; 1168 case Node::ATTRIBUTE_NODE: 1169 case Node::DOCUMENT_FRAGMENT_NODE: 1170 case Node::DOCUMENT_NODE: 1171 case Node::ELEMENT_NODE: 1172 case Node::ENTITY_REFERENCE_NODE: 1173 case Node::XPATH_NAMESPACE_NODE: { 1174 if (!offset) 1175 return 0; 1176 Node* childBefore = n->childNode(offset - 1); 1177 if (!childBefore) 1178 ec = INDEX_SIZE_ERR; 1179 return childBefore; 1180 } 1181 } 1182 ASSERT_NOT_REACHED(); 1183 return 0; 1184} 1185 1186void Range::checkNodeBA(Node* n, ExceptionCode& ec) const 1187{ 1188 // INVALID_NODE_TYPE_ERR: Raised if the root container of refNode is not an 1189 // Attr, Document, DocumentFragment or ShadowRoot node, or part of a SVG shadow DOM tree, 1190 // or if refNode is a Document, DocumentFragment, ShadowRoot, Attr, Entity, or Notation node. 1191 1192 switch (n->nodeType()) { 1193 case Node::ATTRIBUTE_NODE: 1194 case Node::DOCUMENT_FRAGMENT_NODE: 1195 case Node::DOCUMENT_NODE: 1196 case Node::ENTITY_NODE: 1197 case Node::NOTATION_NODE: 1198 ec = RangeException::INVALID_NODE_TYPE_ERR; 1199 return; 1200 case Node::CDATA_SECTION_NODE: 1201 case Node::COMMENT_NODE: 1202 case Node::DOCUMENT_TYPE_NODE: 1203 case Node::ELEMENT_NODE: 1204 case Node::ENTITY_REFERENCE_NODE: 1205 case Node::PROCESSING_INSTRUCTION_NODE: 1206 case Node::TEXT_NODE: 1207 case Node::XPATH_NAMESPACE_NODE: 1208 break; 1209 } 1210 1211 Node* root = n; 1212 while (ContainerNode* parent = root->parentNode()) 1213 root = parent; 1214 1215 switch (root->nodeType()) { 1216 case Node::ATTRIBUTE_NODE: 1217 case Node::DOCUMENT_NODE: 1218 case Node::DOCUMENT_FRAGMENT_NODE: 1219 break; 1220 case Node::CDATA_SECTION_NODE: 1221 case Node::COMMENT_NODE: 1222 case Node::DOCUMENT_TYPE_NODE: 1223 case Node::ELEMENT_NODE: 1224 case Node::ENTITY_NODE: 1225 case Node::ENTITY_REFERENCE_NODE: 1226 case Node::NOTATION_NODE: 1227 case Node::PROCESSING_INSTRUCTION_NODE: 1228 case Node::TEXT_NODE: 1229 case Node::XPATH_NAMESPACE_NODE: 1230 ec = RangeException::INVALID_NODE_TYPE_ERR; 1231 return; 1232 } 1233} 1234 1235PassRefPtr<Range> Range::cloneRange(ExceptionCode& ec) const 1236{ 1237 if (!m_start.container()) { 1238 ec = INVALID_STATE_ERR; 1239 return 0; 1240 } 1241 1242 return Range::create(ownerDocument(), m_start.container(), m_start.offset(), m_end.container(), m_end.offset()); 1243} 1244 1245void Range::setStartAfter(Node* refNode, ExceptionCode& ec) 1246{ 1247 if (!m_start.container()) { 1248 ec = INVALID_STATE_ERR; 1249 return; 1250 } 1251 1252 if (!refNode) { 1253 ec = NOT_FOUND_ERR; 1254 return; 1255 } 1256 1257 ec = 0; 1258 checkNodeBA(refNode, ec); 1259 if (ec) 1260 return; 1261 1262 setStart(refNode->parentNode(), refNode->nodeIndex() + 1, ec); 1263} 1264 1265void Range::setEndBefore(Node* refNode, ExceptionCode& ec) 1266{ 1267 if (!m_start.container()) { 1268 ec = INVALID_STATE_ERR; 1269 return; 1270 } 1271 1272 if (!refNode) { 1273 ec = NOT_FOUND_ERR; 1274 return; 1275 } 1276 1277 ec = 0; 1278 checkNodeBA(refNode, ec); 1279 if (ec) 1280 return; 1281 1282 setEnd(refNode->parentNode(), refNode->nodeIndex(), ec); 1283} 1284 1285void Range::setEndAfter(Node* refNode, ExceptionCode& ec) 1286{ 1287 if (!m_start.container()) { 1288 ec = INVALID_STATE_ERR; 1289 return; 1290 } 1291 1292 if (!refNode) { 1293 ec = NOT_FOUND_ERR; 1294 return; 1295 } 1296 1297 ec = 0; 1298 checkNodeBA(refNode, ec); 1299 if (ec) 1300 return; 1301 1302 setEnd(refNode->parentNode(), refNode->nodeIndex() + 1, ec); 1303} 1304 1305void Range::selectNode(Node* refNode, ExceptionCode& ec) 1306{ 1307 if (!m_start.container()) { 1308 ec = INVALID_STATE_ERR; 1309 return; 1310 } 1311 1312 if (!refNode) { 1313 ec = NOT_FOUND_ERR; 1314 return; 1315 } 1316 1317 // INVALID_NODE_TYPE_ERR: Raised if an ancestor of refNode is an Entity, Notation or 1318 // DocumentType node or if refNode is a Document, DocumentFragment, ShadowRoot, Attr, Entity, or Notation 1319 // node. 1320 for (ContainerNode* anc = refNode->parentNode(); anc; anc = anc->parentNode()) { 1321 switch (anc->nodeType()) { 1322 case Node::ATTRIBUTE_NODE: 1323 case Node::CDATA_SECTION_NODE: 1324 case Node::COMMENT_NODE: 1325 case Node::DOCUMENT_FRAGMENT_NODE: 1326 case Node::DOCUMENT_NODE: 1327 case Node::ELEMENT_NODE: 1328 case Node::ENTITY_REFERENCE_NODE: 1329 case Node::PROCESSING_INSTRUCTION_NODE: 1330 case Node::TEXT_NODE: 1331 case Node::XPATH_NAMESPACE_NODE: 1332 break; 1333 case Node::DOCUMENT_TYPE_NODE: 1334 case Node::ENTITY_NODE: 1335 case Node::NOTATION_NODE: 1336 ec = RangeException::INVALID_NODE_TYPE_ERR; 1337 return; 1338 } 1339 } 1340 1341 switch (refNode->nodeType()) { 1342 case Node::CDATA_SECTION_NODE: 1343 case Node::COMMENT_NODE: 1344 case Node::DOCUMENT_TYPE_NODE: 1345 case Node::ELEMENT_NODE: 1346 case Node::ENTITY_REFERENCE_NODE: 1347 case Node::PROCESSING_INSTRUCTION_NODE: 1348 case Node::TEXT_NODE: 1349 case Node::XPATH_NAMESPACE_NODE: 1350 break; 1351 case Node::ATTRIBUTE_NODE: 1352 case Node::DOCUMENT_FRAGMENT_NODE: 1353 case Node::DOCUMENT_NODE: 1354 case Node::ENTITY_NODE: 1355 case Node::NOTATION_NODE: 1356 ec = RangeException::INVALID_NODE_TYPE_ERR; 1357 return; 1358 } 1359 1360 if (&ownerDocument() != &refNode->document()) 1361 setDocument(refNode->document()); 1362 1363 ec = 0; 1364 setStartBefore(refNode, ec); 1365 if (ec) 1366 return; 1367 setEndAfter(refNode, ec); 1368} 1369 1370void Range::selectNodeContents(Node* refNode, ExceptionCode& ec) 1371{ 1372 if (!m_start.container()) { 1373 ec = INVALID_STATE_ERR; 1374 return; 1375 } 1376 1377 if (!refNode) { 1378 ec = NOT_FOUND_ERR; 1379 return; 1380 } 1381 1382 // INVALID_NODE_TYPE_ERR: Raised if refNode or an ancestor of refNode is an Entity, Notation 1383 // or DocumentType node. 1384 for (Node* n = refNode; n; n = n->parentNode()) { 1385 switch (n->nodeType()) { 1386 case Node::ATTRIBUTE_NODE: 1387 case Node::CDATA_SECTION_NODE: 1388 case Node::COMMENT_NODE: 1389 case Node::DOCUMENT_FRAGMENT_NODE: 1390 case Node::DOCUMENT_NODE: 1391 case Node::ELEMENT_NODE: 1392 case Node::ENTITY_REFERENCE_NODE: 1393 case Node::PROCESSING_INSTRUCTION_NODE: 1394 case Node::TEXT_NODE: 1395 case Node::XPATH_NAMESPACE_NODE: 1396 break; 1397 case Node::DOCUMENT_TYPE_NODE: 1398 case Node::ENTITY_NODE: 1399 case Node::NOTATION_NODE: 1400 ec = RangeException::INVALID_NODE_TYPE_ERR; 1401 return; 1402 } 1403 } 1404 1405 if (&ownerDocument() != &refNode->document()) 1406 setDocument(refNode->document()); 1407 1408 m_start.setToStartOfNode(refNode); 1409 m_end.setToEndOfNode(refNode); 1410} 1411 1412void Range::surroundContents(PassRefPtr<Node> passNewParent, ExceptionCode& ec) 1413{ 1414 RefPtr<Node> newParent = passNewParent; 1415 1416 if (!m_start.container()) { 1417 ec = INVALID_STATE_ERR; 1418 return; 1419 } 1420 1421 if (!newParent) { 1422 ec = NOT_FOUND_ERR; 1423 return; 1424 } 1425 1426 // INVALID_NODE_TYPE_ERR: Raised if node is an Attr, Entity, DocumentType, Notation, 1427 // Document, or DocumentFragment node. 1428 switch (newParent->nodeType()) { 1429 case Node::ATTRIBUTE_NODE: 1430 case Node::DOCUMENT_FRAGMENT_NODE: 1431 case Node::DOCUMENT_NODE: 1432 case Node::DOCUMENT_TYPE_NODE: 1433 case Node::ENTITY_NODE: 1434 case Node::NOTATION_NODE: 1435 ec = RangeException::INVALID_NODE_TYPE_ERR; 1436 return; 1437 case Node::CDATA_SECTION_NODE: 1438 case Node::COMMENT_NODE: 1439 case Node::ELEMENT_NODE: 1440 case Node::ENTITY_REFERENCE_NODE: 1441 case Node::PROCESSING_INSTRUCTION_NODE: 1442 case Node::TEXT_NODE: 1443 case Node::XPATH_NAMESPACE_NODE: 1444 break; 1445 } 1446 1447 // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of 1448 // the Range is read-only. 1449 if (containedByReadOnly()) { 1450 ec = NO_MODIFICATION_ALLOWED_ERR; 1451 return; 1452 } 1453 1454 // Raise a HIERARCHY_REQUEST_ERR if m_start.container() doesn't accept children like newParent. 1455 Node* parentOfNewParent = m_start.container(); 1456 1457 // If m_start.container() is a character data node, it will be split and it will be its parent that will 1458 // need to accept newParent (or in the case of a comment, it logically "would" be inserted into the parent, 1459 // although this will fail below for another reason). 1460 if (parentOfNewParent->isCharacterDataNode()) 1461 parentOfNewParent = parentOfNewParent->parentNode(); 1462 if (!parentOfNewParent || !parentOfNewParent->childTypeAllowed(newParent->nodeType())) { 1463 ec = HIERARCHY_REQUEST_ERR; 1464 return; 1465 } 1466 1467 if (newParent->contains(m_start.container())) { 1468 ec = HIERARCHY_REQUEST_ERR; 1469 return; 1470 } 1471 1472 // FIXME: Do we need a check if the node would end up with a child node of a type not 1473 // allowed by the type of node? 1474 1475 // BAD_BOUNDARYPOINTS_ERR: Raised if the Range partially selects a non-Text node. 1476 Node* startNonTextContainer = m_start.container(); 1477 if (startNonTextContainer->nodeType() == Node::TEXT_NODE) 1478 startNonTextContainer = startNonTextContainer->parentNode(); 1479 Node* endNonTextContainer = m_end.container(); 1480 if (endNonTextContainer->nodeType() == Node::TEXT_NODE) 1481 endNonTextContainer = endNonTextContainer->parentNode(); 1482 if (startNonTextContainer != endNonTextContainer) { 1483 ec = RangeException::BAD_BOUNDARYPOINTS_ERR; 1484 return; 1485 } 1486 1487 ec = 0; 1488 while (Node* n = newParent->firstChild()) { 1489 toContainerNode(newParent.get())->removeChild(n, ec); 1490 if (ec) 1491 return; 1492 } 1493 RefPtr<DocumentFragment> fragment = extractContents(ec); 1494 if (ec) 1495 return; 1496 insertNode(newParent, ec); 1497 if (ec) 1498 return; 1499 newParent->appendChild(fragment.release(), ec); 1500 if (ec) 1501 return; 1502 selectNode(newParent.get(), ec); 1503} 1504 1505void Range::setStartBefore(Node* refNode, ExceptionCode& ec) 1506{ 1507 if (!m_start.container()) { 1508 ec = INVALID_STATE_ERR; 1509 return; 1510 } 1511 1512 if (!refNode) { 1513 ec = NOT_FOUND_ERR; 1514 return; 1515 } 1516 1517 ec = 0; 1518 checkNodeBA(refNode, ec); 1519 if (ec) 1520 return; 1521 1522 setStart(refNode->parentNode(), refNode->nodeIndex(), ec); 1523} 1524 1525void Range::checkDeleteExtract(ExceptionCode& ec) 1526{ 1527 if (!m_start.container()) { 1528 ec = INVALID_STATE_ERR; 1529 return; 1530 } 1531 1532 ec = 0; 1533 if (!commonAncestorContainer(ec) || ec) 1534 return; 1535 1536 Node* pastLast = pastLastNode(); 1537 for (Node* n = firstNode(); n != pastLast; n = NodeTraversal::next(n)) { 1538 if (n->isReadOnlyNode()) { 1539 ec = NO_MODIFICATION_ALLOWED_ERR; 1540 return; 1541 } 1542 if (n->nodeType() == Node::DOCUMENT_TYPE_NODE) { 1543 ec = HIERARCHY_REQUEST_ERR; 1544 return; 1545 } 1546 } 1547 1548 if (containedByReadOnly()) { 1549 ec = NO_MODIFICATION_ALLOWED_ERR; 1550 return; 1551 } 1552} 1553 1554bool Range::containedByReadOnly() const 1555{ 1556 for (Node* n = m_start.container(); n; n = n->parentNode()) { 1557 if (n->isReadOnlyNode()) 1558 return true; 1559 } 1560 for (Node* n = m_end.container(); n; n = n->parentNode()) { 1561 if (n->isReadOnlyNode()) 1562 return true; 1563 } 1564 return false; 1565} 1566 1567Node* Range::firstNode() const 1568{ 1569 if (!m_start.container()) 1570 return 0; 1571 if (m_start.container()->offsetInCharacters()) 1572 return m_start.container(); 1573 if (Node* child = m_start.container()->childNode(m_start.offset())) 1574 return child; 1575 if (!m_start.offset()) 1576 return m_start.container(); 1577 return NodeTraversal::nextSkippingChildren(m_start.container()); 1578} 1579 1580ShadowRoot* Range::shadowRoot() const 1581{ 1582 return startContainer() ? startContainer()->containingShadowRoot() : 0; 1583} 1584 1585Node* Range::pastLastNode() const 1586{ 1587 if (!m_start.container() || !m_end.container()) 1588 return 0; 1589 if (m_end.container()->offsetInCharacters()) 1590 return NodeTraversal::nextSkippingChildren(m_end.container()); 1591 if (Node* child = m_end.container()->childNode(m_end.offset())) 1592 return child; 1593 return NodeTraversal::nextSkippingChildren(m_end.container()); 1594} 1595 1596IntRect Range::boundingBox() const 1597{ 1598 IntRect result; 1599 Vector<IntRect> rects; 1600 textRects(rects); 1601 const size_t n = rects.size(); 1602 for (size_t i = 0; i < n; ++i) 1603 result.unite(rects[i]); 1604 return result; 1605} 1606 1607void Range::textRects(Vector<IntRect>& rects, bool useSelectionHeight, RangeInFixedPosition* inFixed) const 1608{ 1609 Node* startContainer = m_start.container(); 1610 Node* endContainer = m_end.container(); 1611 1612 if (!startContainer || !endContainer) { 1613 if (inFixed) 1614 *inFixed = NotFixedPosition; 1615 return; 1616 } 1617 1618 bool allFixed = true; 1619 bool someFixed = false; 1620 1621 Node* stopNode = pastLastNode(); 1622 for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) { 1623 RenderObject* r = node->renderer(); 1624 if (!r) 1625 continue; 1626 bool isFixed = false; 1627 if (r->isBR()) 1628 r->absoluteRects(rects, flooredLayoutPoint(r->localToAbsolute())); 1629 else if (r->isText()) { 1630 int startOffset = node == startContainer ? m_start.offset() : 0; 1631 int endOffset = node == endContainer ? m_end.offset() : std::numeric_limits<int>::max(); 1632 rects.appendVector(toRenderText(r)->absoluteRectsForRange(startOffset, endOffset, useSelectionHeight, &isFixed)); 1633 } else 1634 continue; 1635 allFixed &= isFixed; 1636 someFixed |= isFixed; 1637 } 1638 1639 if (inFixed) 1640 *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition); 1641} 1642 1643void Range::textQuads(Vector<FloatQuad>& quads, bool useSelectionHeight, RangeInFixedPosition* inFixed) const 1644{ 1645 Node* startContainer = m_start.container(); 1646 Node* endContainer = m_end.container(); 1647 1648 if (!startContainer || !endContainer) { 1649 if (inFixed) 1650 *inFixed = NotFixedPosition; 1651 return; 1652 } 1653 1654 bool allFixed = true; 1655 bool someFixed = false; 1656 1657 Node* stopNode = pastLastNode(); 1658 for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) { 1659 RenderObject* r = node->renderer(); 1660 if (!r) 1661 continue; 1662 bool isFixed = false; 1663 if (r->isBR()) 1664 r->absoluteQuads(quads, &isFixed); 1665 else if (r->isText()) { 1666 int startOffset = node == startContainer ? m_start.offset() : 0; 1667 int endOffset = node == endContainer ? m_end.offset() : std::numeric_limits<int>::max(); 1668 quads.appendVector(toRenderText(r)->absoluteQuadsForRange(startOffset, endOffset, useSelectionHeight, &isFixed)); 1669 } else 1670 continue; 1671 allFixed &= isFixed; 1672 someFixed |= isFixed; 1673 } 1674 1675 if (inFixed) 1676 *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition); 1677} 1678 1679#if PLATFORM(IOS) 1680static bool intervalsSufficientlyOverlap(int startA, int endA, int startB, int endB) 1681{ 1682 if (endA <= startA || endB <= startB) 1683 return false; 1684 1685 const float sufficientOverlap = .75; 1686 1687 int lengthA = endA - startA; 1688 int lengthB = endB - startB; 1689 1690 int maxStart = std::max(startA, startB); 1691 int minEnd = std::min(endA, endB); 1692 1693 if (maxStart > minEnd) 1694 return false; 1695 1696 return minEnd - maxStart >= sufficientOverlap * std::min(lengthA, lengthB); 1697} 1698 1699static inline void adjustLineHeightOfSelectionRects(Vector<SelectionRect>& rects, size_t numberOfRects, int lineNumber, int lineTop, int lineHeight) 1700{ 1701 ASSERT(rects.size() >= numberOfRects); 1702 for (size_t i = numberOfRects; i; ) { 1703 --i; 1704 if (rects[i].lineNumber()) 1705 break; 1706 rects[i].setLineNumber(lineNumber); 1707 rects[i].setLogicalTop(lineTop); 1708 rects[i].setLogicalHeight(lineHeight); 1709 } 1710} 1711 1712static SelectionRect coalesceSelectionRects(const SelectionRect& original, const SelectionRect& previous) 1713{ 1714 SelectionRect result(unionRect(previous.rect(), original.rect()), original.isHorizontal(), original.pageNumber()); 1715 result.setDirection(original.containsStart() || original.containsEnd() ? original.direction() : previous.direction()); 1716 result.setContainsStart(previous.containsStart() || original.containsStart()); 1717 result.setContainsEnd(previous.containsEnd() || original.containsEnd()); 1718 result.setIsFirstOnLine(previous.isFirstOnLine() || original.isFirstOnLine()); 1719 result.setIsLastOnLine(previous.isLastOnLine() || original.isLastOnLine()); 1720 return result; 1721} 1722 1723// This function is similar in spirit to addLineBoxRects, but annotates the returned rectangles 1724// with additional state which helps iOS draw selections in its unique way. 1725void Range::collectSelectionRects(Vector<SelectionRect>& rects) 1726{ 1727 if (!m_start.container() || !m_end.container()) 1728 return; 1729 1730 Node* startContainer = m_start.container(); 1731 Node* endContainer = m_end.container(); 1732 int startOffset = m_start.offset(); 1733 int endOffset = m_end.offset(); 1734 1735 Vector<SelectionRect> newRects; 1736 Node* stopNode = pastLastNode(); 1737 bool hasFlippedWritingMode = startContainer->renderer() && startContainer->renderer()->style().isFlippedBlocksWritingMode(); 1738 bool containsDifferentWritingModes = false; 1739 for (Node* node = firstNode(); node && node != stopNode; node = NodeTraversal::next(node)) { 1740 RenderObject* renderer = node->renderer(); 1741 // Only ask leaf render objects for their line box rects. 1742 if (renderer && !renderer->firstChildSlow() && renderer->style().userSelect() != SELECT_NONE) { 1743 bool isStartNode = renderer->node() == startContainer; 1744 bool isEndNode = renderer->node() == endContainer; 1745 if (hasFlippedWritingMode != renderer->style().isFlippedBlocksWritingMode()) 1746 containsDifferentWritingModes = true; 1747 // FIXME: Sending 0 for the startOffset is a weird way of telling the renderer that the selection 1748 // doesn't start inside it, since we'll also send 0 if the selection *does* start in it, at offset 0. 1749 // 1750 // FIXME: Selection endpoints aren't always inside leaves, and we only build SelectionRects for leaves, 1751 // so we can't accurately determine which SelectionRects contain the selection start and end using 1752 // only the offsets of the start and end. We need to pass the whole Range. 1753 int beginSelectionOffset = isStartNode ? startOffset : 0; 1754 int endSelectionOffset = isEndNode ? endOffset : std::numeric_limits<int>::max(); 1755 renderer->collectSelectionRects(newRects, beginSelectionOffset, endSelectionOffset); 1756 size_t numberOfNewRects = newRects.size(); 1757 for (size_t i = 0; i < numberOfNewRects; ++i) { 1758 SelectionRect& selectionRect = newRects[i]; 1759 if (selectionRect.containsStart() && !isStartNode) 1760 selectionRect.setContainsStart(false); 1761 if (selectionRect.containsEnd() && !isEndNode) 1762 selectionRect.setContainsEnd(false); 1763 if (selectionRect.logicalWidth() || selectionRect.logicalHeight()) 1764 rects.append(newRects[i]); 1765 } 1766 newRects.shrink(0); 1767 } 1768 } 1769 1770 // The range could span over nodes with different writing modes. 1771 // If this is the case, we use the writing mode of the common ancestor. 1772 if (containsDifferentWritingModes) { 1773 if (Node* ancestor = commonAncestorContainer(startContainer, endContainer)) 1774 hasFlippedWritingMode = ancestor->renderer()->style().isFlippedBlocksWritingMode(); 1775 } 1776 1777 const size_t numberOfRects = rects.size(); 1778 1779 // If the selection ends in a BR, then add the line break bit to the last 1780 // rect we have. This will cause its selection rect to extend to the 1781 // end of the line. 1782 if (stopNode && stopNode->hasTagName(HTMLNames::brTag) && numberOfRects) { 1783 // Only set the line break bit if the end of the range actually 1784 // extends all the way to include the <br>. VisiblePosition helps to 1785 // figure this out. 1786 VisiblePosition endPosition(createLegacyEditingPosition(endContainer, endOffset), VP_DEFAULT_AFFINITY); 1787 VisiblePosition brPosition(createLegacyEditingPosition(stopNode, 0), VP_DEFAULT_AFFINITY); 1788 if (endPosition == brPosition) 1789 rects.last().setIsLineBreak(true); 1790 } 1791 1792 int lineTop = std::numeric_limits<int>::max(); 1793 int lineBottom = std::numeric_limits<int>::min(); 1794 int lastLineTop = lineTop; 1795 int lastLineBottom = lineBottom; 1796 int lineNumber = 0; 1797 1798 for (size_t i = 0; i < numberOfRects; ++i) { 1799 int currentRectTop = rects[i].logicalTop(); 1800 int currentRectBottom = currentRectTop + rects[i].logicalHeight(); 1801 1802 // We don't want to count the ruby text as a separate line. 1803 if (intervalsSufficientlyOverlap(currentRectTop, currentRectBottom, lineTop, lineBottom) || (i && rects[i].isRubyText())) { 1804 // Grow the current line bounds. 1805 lineTop = std::min(lineTop, currentRectTop); 1806 lineBottom = std::max(lineBottom, currentRectBottom); 1807 // Avoid overlap with the previous line. 1808 if (!hasFlippedWritingMode) 1809 lineTop = std::max(lastLineBottom, lineTop); 1810 else 1811 lineBottom = std::min(lastLineTop, lineBottom); 1812 } else { 1813 adjustLineHeightOfSelectionRects(rects, i, lineNumber, lineTop, lineBottom - lineTop); 1814 if (!hasFlippedWritingMode) { 1815 lastLineTop = lineTop; 1816 if (currentRectBottom >= lastLineTop) { 1817 lastLineBottom = lineBottom; 1818 lineTop = lastLineBottom; 1819 } else { 1820 lineTop = currentRectTop; 1821 lastLineBottom = std::numeric_limits<int>::min(); 1822 } 1823 lineBottom = currentRectBottom; 1824 } else { 1825 lastLineBottom = lineBottom; 1826 if (currentRectTop <= lastLineBottom && i && rects[i].pageNumber() == rects[i - 1].pageNumber()) { 1827 lastLineTop = lineTop; 1828 lineBottom = lastLineTop; 1829 } else { 1830 lastLineTop = std::numeric_limits<int>::max(); 1831 lineBottom = currentRectBottom; 1832 } 1833 lineTop = currentRectTop; 1834 } 1835 ++lineNumber; 1836 } 1837 } 1838 1839 // Adjust line height. 1840 adjustLineHeightOfSelectionRects(rects, numberOfRects, lineNumber, lineTop, lineBottom - lineTop); 1841 1842 // Sort the rectangles and make sure there are no gaps. The rectangles could be unsorted when 1843 // there is ruby text and we could have gaps on the line when adjacent elements on the line 1844 // have a different orientation. 1845 size_t firstRectWithCurrentLineNumber = 0; 1846 for (size_t currentRect = 1; currentRect < numberOfRects; ++currentRect) { 1847 if (rects[currentRect].lineNumber() != rects[currentRect - 1].lineNumber()) { 1848 firstRectWithCurrentLineNumber = currentRect; 1849 continue; 1850 } 1851 if (rects[currentRect].logicalLeft() >= rects[currentRect - 1].logicalLeft()) 1852 continue; 1853 1854 SelectionRect selectionRect = rects[currentRect]; 1855 size_t i; 1856 for (i = currentRect; i > firstRectWithCurrentLineNumber && selectionRect.logicalLeft() < rects[i - 1].logicalLeft(); --i) 1857 rects[i] = rects[i - 1]; 1858 rects[i] = selectionRect; 1859 } 1860 1861 for (size_t j = 1; j < numberOfRects; ++j) { 1862 if (rects[j].lineNumber() != rects[j - 1].lineNumber()) 1863 continue; 1864 SelectionRect& previousRect = rects[j - 1]; 1865 bool previousRectMayNotReachRightEdge = (previousRect.direction() == LTR && previousRect.containsEnd()) || (previousRect.direction() == RTL && previousRect.containsStart()); 1866 if (previousRectMayNotReachRightEdge) 1867 continue; 1868 int adjustedWidth = rects[j].logicalLeft() - previousRect.logicalLeft(); 1869 if (adjustedWidth > previousRect.logicalWidth()) 1870 previousRect.setLogicalWidth(adjustedWidth); 1871 } 1872 1873 int maxLineNumber = lineNumber; 1874 1875 // Extend rects out to edges as needed. 1876 for (size_t i = 0; i < numberOfRects; ++i) { 1877 SelectionRect& selectionRect = rects[i]; 1878 if (!selectionRect.isLineBreak() && selectionRect.lineNumber() >= maxLineNumber) 1879 continue; 1880 if (selectionRect.direction() == RTL && selectionRect.isFirstOnLine()) { 1881 selectionRect.setLogicalWidth(selectionRect.logicalWidth() + selectionRect.logicalLeft() - selectionRect.minX()); 1882 selectionRect.setLogicalLeft(selectionRect.minX()); 1883 } else if (selectionRect.direction() == LTR && selectionRect.isLastOnLine()) 1884 selectionRect.setLogicalWidth(selectionRect.maxX() - selectionRect.logicalLeft()); 1885 } 1886 1887 // Union all the rectangles on interior lines (i.e. not first or last). 1888 // On first and last lines, just avoid having overlaps by merging intersecting rectangles. 1889 Vector<SelectionRect> unionedRects; 1890 IntRect interiorUnionRect; 1891 for (size_t i = 0; i < numberOfRects; ++i) { 1892 SelectionRect& currentRect = rects[i]; 1893 if (currentRect.lineNumber() == 1) { 1894 ASSERT(interiorUnionRect.isEmpty()); 1895 if (!unionedRects.isEmpty()) { 1896 SelectionRect& previousRect = unionedRects.last(); 1897 if (previousRect.rect().intersects(currentRect.rect())) { 1898 previousRect = coalesceSelectionRects(currentRect, previousRect); 1899 continue; 1900 } 1901 } 1902 // Couldn't merge with previous rect, so just appending. 1903 unionedRects.append(currentRect); 1904 } else if (currentRect.lineNumber() < maxLineNumber) { 1905 if (interiorUnionRect.isEmpty()) { 1906 // Start collecting interior rects. 1907 interiorUnionRect = currentRect.rect(); 1908 } else if (interiorUnionRect.intersects(currentRect.rect()) 1909 || interiorUnionRect.maxX() == currentRect.rect().x() 1910 || interiorUnionRect.maxY() == currentRect.rect().y() 1911 || interiorUnionRect.x() == currentRect.rect().maxX() 1912 || interiorUnionRect.y() == currentRect.rect().maxY()) { 1913 // Only union the lines that are attached. 1914 // For iBooks, the interior lines may cross multiple horizontal pages. 1915 interiorUnionRect.unite(currentRect.rect()); 1916 } else { 1917 unionedRects.append(SelectionRect(interiorUnionRect, currentRect.isHorizontal(), currentRect.pageNumber())); 1918 interiorUnionRect = currentRect.rect(); 1919 } 1920 } else { 1921 // Processing last line. 1922 if (!interiorUnionRect.isEmpty()) { 1923 unionedRects.append(SelectionRect(interiorUnionRect, currentRect.isHorizontal(), currentRect.pageNumber())); 1924 interiorUnionRect = IntRect(); 1925 } 1926 1927 ASSERT(!unionedRects.isEmpty()); 1928 SelectionRect& previousRect = unionedRects.last(); 1929 if (previousRect.logicalTop() == currentRect.logicalTop() && previousRect.rect().intersects(currentRect.rect())) { 1930 // previousRect is also on the last line, and intersects the current one. 1931 previousRect = coalesceSelectionRects(currentRect, previousRect); 1932 continue; 1933 } 1934 // Couldn't merge with previous rect, so just appending. 1935 unionedRects.append(currentRect); 1936 } 1937 } 1938 1939 rects.swap(unionedRects); 1940} 1941#endif 1942 1943#ifndef NDEBUG 1944void Range::formatForDebugger(char* buffer, unsigned length) const 1945{ 1946 StringBuilder result; 1947 String s; 1948 1949 if (!m_start.container() || !m_end.container()) 1950 result.appendLiteral("<empty>"); 1951 else { 1952 const int FormatBufferSize = 1024; 1953 char s[FormatBufferSize]; 1954 result.appendLiteral("from offset "); 1955 result.appendNumber(m_start.offset()); 1956 result.appendLiteral(" of "); 1957 m_start.container()->formatForDebugger(s, FormatBufferSize); 1958 result.append(s); 1959 result.appendLiteral(" to offset "); 1960 result.appendNumber(m_end.offset()); 1961 result.appendLiteral(" of "); 1962 m_end.container()->formatForDebugger(s, FormatBufferSize); 1963 result.append(s); 1964 } 1965 1966 strncpy(buffer, result.toString().utf8().data(), length - 1); 1967} 1968#endif 1969 1970bool Range::contains(const Range& other) const 1971{ 1972 if (commonAncestorContainer(ASSERT_NO_EXCEPTION)->ownerDocument() != other.commonAncestorContainer(ASSERT_NO_EXCEPTION)->ownerDocument()) 1973 return false; 1974 1975 short startToStart = compareBoundaryPoints(Range::START_TO_START, &other, ASSERT_NO_EXCEPTION); 1976 if (startToStart > 0) 1977 return false; 1978 1979 short endToEnd = compareBoundaryPoints(Range::END_TO_END, &other, ASSERT_NO_EXCEPTION); 1980 return endToEnd >= 0; 1981} 1982 1983bool areRangesEqual(const Range* a, const Range* b) 1984{ 1985 if (a == b) 1986 return true; 1987 if (!a || !b) 1988 return false; 1989 return a->startPosition() == b->startPosition() && a->endPosition() == b->endPosition(); 1990} 1991 1992bool rangesOverlap(const Range* a, const Range* b) 1993{ 1994 if (!a || !b) 1995 return false; 1996 1997 if (a == b) 1998 return true; 1999 2000 if (a->commonAncestorContainer(ASSERT_NO_EXCEPTION)->ownerDocument() != b->commonAncestorContainer(ASSERT_NO_EXCEPTION)->ownerDocument()) 2001 return false; 2002 2003 short startToStart = a->compareBoundaryPoints(Range::START_TO_START, b, ASSERT_NO_EXCEPTION); 2004 short endToEnd = a->compareBoundaryPoints(Range::END_TO_END, b, ASSERT_NO_EXCEPTION); 2005 2006 // First range contains the second range. 2007 if (startToStart <= 0 && endToEnd >= 0) 2008 return true; 2009 2010 // End of first range is inside second range. 2011 if (a->compareBoundaryPoints(Range::START_TO_END, b, ASSERT_NO_EXCEPTION) >= 0 && endToEnd <= 0) 2012 return true; 2013 2014 // Start of first range is inside second range. 2015 if (startToStart >= 0 && a->compareBoundaryPoints(Range::END_TO_START, b, ASSERT_NO_EXCEPTION) <= 0) 2016 return true; 2017 2018 return false; 2019} 2020 2021PassRefPtr<Range> rangeOfContents(Node& node) 2022{ 2023 RefPtr<Range> range = Range::create(node.document()); 2024 int exception = 0; 2025 range->selectNodeContents(&node, exception); 2026 return range.release(); 2027} 2028 2029int Range::maxStartOffset() const 2030{ 2031 if (!m_start.container()) 2032 return 0; 2033 if (!m_start.container()->offsetInCharacters()) 2034 return m_start.container()->childNodeCount(); 2035 return m_start.container()->maxCharacterOffset(); 2036} 2037 2038int Range::maxEndOffset() const 2039{ 2040 if (!m_end.container()) 2041 return 0; 2042 if (!m_end.container()->offsetInCharacters()) 2043 return m_end.container()->childNodeCount(); 2044 return m_end.container()->maxCharacterOffset(); 2045} 2046 2047static inline void boundaryNodeChildrenChanged(RangeBoundaryPoint& boundary, ContainerNode& container) 2048{ 2049 if (!boundary.childBefore()) 2050 return; 2051 if (boundary.container() != &container) 2052 return; 2053 boundary.invalidateOffset(); 2054} 2055 2056void Range::nodeChildrenChanged(ContainerNode& container) 2057{ 2058 ASSERT(&container.document() == &ownerDocument()); 2059 boundaryNodeChildrenChanged(m_start, container); 2060 boundaryNodeChildrenChanged(m_end, container); 2061} 2062 2063static inline void boundaryNodeChildrenWillBeRemoved(RangeBoundaryPoint& boundary, ContainerNode& container) 2064{ 2065 for (Node* nodeToBeRemoved = container.firstChild(); nodeToBeRemoved; nodeToBeRemoved = nodeToBeRemoved->nextSibling()) { 2066 if (boundary.childBefore() == nodeToBeRemoved) { 2067 boundary.setToStartOfNode(&container); 2068 return; 2069 } 2070 2071 for (Node* n = boundary.container(); n; n = n->parentNode()) { 2072 if (n == nodeToBeRemoved) { 2073 boundary.setToStartOfNode(&container); 2074 return; 2075 } 2076 } 2077 } 2078} 2079 2080void Range::nodeChildrenWillBeRemoved(ContainerNode& container) 2081{ 2082 ASSERT(&container.document() == &ownerDocument()); 2083 boundaryNodeChildrenWillBeRemoved(m_start, container); 2084 boundaryNodeChildrenWillBeRemoved(m_end, container); 2085} 2086 2087static inline void boundaryNodeWillBeRemoved(RangeBoundaryPoint& boundary, Node* nodeToBeRemoved) 2088{ 2089 if (boundary.childBefore() == nodeToBeRemoved) { 2090 boundary.childBeforeWillBeRemoved(); 2091 return; 2092 } 2093 2094 for (Node* n = boundary.container(); n; n = n->parentNode()) { 2095 if (n == nodeToBeRemoved) { 2096 boundary.setToBeforeChild(nodeToBeRemoved); 2097 return; 2098 } 2099 } 2100} 2101 2102void Range::nodeWillBeRemoved(Node* node) 2103{ 2104 ASSERT(node); 2105 ASSERT(&node->document() == &ownerDocument()); 2106 ASSERT(node != &ownerDocument()); 2107 ASSERT(node->parentNode()); 2108 boundaryNodeWillBeRemoved(m_start, node); 2109 boundaryNodeWillBeRemoved(m_end, node); 2110} 2111 2112static inline void boundaryTextInserted(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length) 2113{ 2114 if (boundary.container() != text) 2115 return; 2116 unsigned boundaryOffset = boundary.offset(); 2117 if (offset >= boundaryOffset) 2118 return; 2119 boundary.setOffset(boundaryOffset + length); 2120} 2121 2122void Range::textInserted(Node* text, unsigned offset, unsigned length) 2123{ 2124 ASSERT(text); 2125 ASSERT(&text->document() == &ownerDocument()); 2126 boundaryTextInserted(m_start, text, offset, length); 2127 boundaryTextInserted(m_end, text, offset, length); 2128} 2129 2130static inline void boundaryTextRemoved(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length) 2131{ 2132 if (boundary.container() != text) 2133 return; 2134 unsigned boundaryOffset = boundary.offset(); 2135 if (offset >= boundaryOffset) 2136 return; 2137 if (offset + length >= boundaryOffset) 2138 boundary.setOffset(offset); 2139 else 2140 boundary.setOffset(boundaryOffset - length); 2141} 2142 2143void Range::textRemoved(Node* text, unsigned offset, unsigned length) 2144{ 2145 ASSERT(text); 2146 ASSERT(&text->document() == &ownerDocument()); 2147 boundaryTextRemoved(m_start, text, offset, length); 2148 boundaryTextRemoved(m_end, text, offset, length); 2149} 2150 2151static inline void boundaryTextNodesMerged(RangeBoundaryPoint& boundary, NodeWithIndex& oldNode, unsigned offset) 2152{ 2153 if (boundary.container() == oldNode.node()) 2154 boundary.set(oldNode.node()->previousSibling(), boundary.offset() + offset, 0); 2155 else if (boundary.container() == oldNode.node()->parentNode() && boundary.offset() == oldNode.index()) 2156 boundary.set(oldNode.node()->previousSibling(), offset, 0); 2157} 2158 2159void Range::textNodesMerged(NodeWithIndex& oldNode, unsigned offset) 2160{ 2161 ASSERT(oldNode.node()); 2162 ASSERT(&oldNode.node()->document() == &ownerDocument()); 2163 ASSERT(oldNode.node()->parentNode()); 2164 ASSERT(oldNode.node()->isTextNode()); 2165 ASSERT(oldNode.node()->previousSibling()); 2166 ASSERT(oldNode.node()->previousSibling()->isTextNode()); 2167 boundaryTextNodesMerged(m_start, oldNode, offset); 2168 boundaryTextNodesMerged(m_end, oldNode, offset); 2169} 2170 2171static inline void boundaryTextNodesSplit(RangeBoundaryPoint& boundary, Text* oldNode) 2172{ 2173 if (boundary.container() != oldNode) 2174 return; 2175 unsigned boundaryOffset = boundary.offset(); 2176 if (boundaryOffset <= oldNode->length()) 2177 return; 2178 boundary.set(oldNode->nextSibling(), boundaryOffset - oldNode->length(), 0); 2179} 2180 2181void Range::textNodeSplit(Text* oldNode) 2182{ 2183 ASSERT(oldNode); 2184 ASSERT(&oldNode->document() == &ownerDocument()); 2185 ASSERT(oldNode->parentNode()); 2186 ASSERT(oldNode->isTextNode()); 2187 ASSERT(oldNode->nextSibling()); 2188 ASSERT(oldNode->nextSibling()->isTextNode()); 2189 boundaryTextNodesSplit(m_start, oldNode); 2190 boundaryTextNodesSplit(m_end, oldNode); 2191} 2192 2193void Range::expand(const String& unit, ExceptionCode& ec) 2194{ 2195 VisiblePosition start(startPosition()); 2196 VisiblePosition end(endPosition()); 2197 if (unit == "word") { 2198 start = startOfWord(start); 2199 end = endOfWord(end); 2200 } else if (unit == "sentence") { 2201 start = startOfSentence(start); 2202 end = endOfSentence(end); 2203 } else if (unit == "block") { 2204 start = startOfParagraph(start); 2205 end = endOfParagraph(end); 2206 } else if (unit == "document") { 2207 start = startOfDocument(start); 2208 end = endOfDocument(end); 2209 } else 2210 return; 2211 setStart(start.deepEquivalent().containerNode(), start.deepEquivalent().computeOffsetInContainerNode(), ec); 2212 setEnd(end.deepEquivalent().containerNode(), end.deepEquivalent().computeOffsetInContainerNode(), ec); 2213} 2214 2215PassRefPtr<ClientRectList> Range::getClientRects() const 2216{ 2217 if (!m_start.container()) 2218 return ClientRectList::create(); 2219 2220 ownerDocument().updateLayoutIgnorePendingStylesheets(); 2221 2222 Vector<FloatQuad> quads; 2223 getBorderAndTextQuads(quads); 2224 2225 return ClientRectList::create(quads); 2226} 2227 2228PassRefPtr<ClientRect> Range::getBoundingClientRect() const 2229{ 2230 return ClientRect::create(boundingRect()); 2231} 2232 2233void Range::getBorderAndTextQuads(Vector<FloatQuad>& quads) const 2234{ 2235 Node* startContainer = m_start.container(); 2236 Node* endContainer = m_end.container(); 2237 Node* stopNode = pastLastNode(); 2238 2239 HashSet<Node*> selectedElementsSet; 2240 for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) { 2241 if (node->isElementNode()) 2242 selectedElementsSet.add(node); 2243 } 2244 2245 // Don't include elements that are only partially selected. 2246 Node* lastNode = m_end.childBefore() ? m_end.childBefore() : endContainer; 2247 for (Node* parent = lastNode->parentNode(); parent; parent = parent->parentNode()) 2248 selectedElementsSet.remove(parent); 2249 2250 for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) { 2251 if (node->isElementNode() && selectedElementsSet.contains(node) && !selectedElementsSet.contains(node->parentNode())) { 2252 if (RenderBoxModelObject* renderBoxModelObject = toElement(node)->renderBoxModelObject()) { 2253 Vector<FloatQuad> elementQuads; 2254 renderBoxModelObject->absoluteQuads(elementQuads); 2255 ownerDocument().adjustFloatQuadsForScrollAndAbsoluteZoomAndFrameScale(elementQuads, renderBoxModelObject->style()); 2256 2257 quads.appendVector(elementQuads); 2258 } 2259 } else if (node->isTextNode()) { 2260 if (RenderObject* renderer = toText(node)->renderer()) { 2261 const RenderText& renderText = toRenderText(*renderer); 2262 int startOffset = (node == startContainer) ? m_start.offset() : 0; 2263 int endOffset = (node == endContainer) ? m_end.offset() : INT_MAX; 2264 2265 auto textQuads = renderText.absoluteQuadsForRange(startOffset, endOffset); 2266 ownerDocument().adjustFloatQuadsForScrollAndAbsoluteZoomAndFrameScale(textQuads, renderText.style()); 2267 2268 quads.appendVector(textQuads); 2269 } 2270 } 2271 } 2272} 2273 2274FloatRect Range::boundingRect() const 2275{ 2276 if (!m_start.container()) 2277 return FloatRect(); 2278 2279 ownerDocument().updateLayoutIgnorePendingStylesheets(); 2280 2281 Vector<FloatQuad> quads; 2282 getBorderAndTextQuads(quads); 2283 if (quads.isEmpty()) 2284 return FloatRect(); 2285 2286 FloatRect result; 2287 for (size_t i = 0; i < quads.size(); ++i) 2288 result.unite(quads[i].boundingBox()); 2289 2290 return result; 2291} 2292 2293} // namespace WebCore 2294 2295#ifndef NDEBUG 2296 2297void showTree(const WebCore::Range* range) 2298{ 2299 if (range && range->boundaryPointsValid()) { 2300 range->startContainer()->showTreeAndMark(range->startContainer(), "S", range->endContainer(), "E"); 2301 fprintf(stderr, "start offset: %d, end offset: %d\n", range->startOffset(), range->endOffset()); 2302 } 2303} 2304 2305#endif 2306