Source/WebCore/dom/Range.cpp

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