src/third_party/WebKit/Source/core/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 "core/dom/Range.h"
  27
  28 #include "bindings/core/v8/ExceptionState.h"
  29 #include "core/dom/ClientRect.h"
  30 #include "core/dom/ClientRectList.h"
  31 #include "core/dom/DocumentFragment.h"
  32 #include "core/dom/ExceptionCode.h"
  33 #include "core/dom/Node.h"
  34 #include "core/dom/NodeTraversal.h"
  35 #include "core/dom/NodeWithIndex.h"
  36 #include "core/dom/ProcessingInstruction.h"
  37 #include "core/dom/Text.h"
  38 #include "core/editing/TextIterator.h"
  39 #include "core/editing/VisiblePosition.h"
  40 #include "core/editing/VisibleUnits.h"
  41 #include "core/editing/markup.h"
  42 #include "core/events/ScopedEventQueue.h"
  43 #include "core/html/HTMLBodyElement.h"
  44 #include "core/html/HTMLElement.h"
  45 #include "core/rendering/RenderBoxModelObject.h"
  46 #include "core/rendering/RenderText.h"
  47 #include "core/svg/SVGSVGElement.h"
  48 #include "platform/geometry/FloatQuad.h"
  49 #include "wtf/RefCountedLeakCounter.h"
  50 #include "wtf/text/CString.h"
  51 #include "wtf/text/StringBuilder.h"
  52 #ifndef NDEBUG
  53 #include <stdio.h>
  54 #endif
  55
  56 namespace blink {
  57
  58 DEFINE_DEBUG_ONLY_GLOBAL(WTF::RefCountedLeakCounter, rangeCounter, ("Range"));
  59
  60 inline Range::Range(Document& ownerDocument)
  61     : m_ownerDocument(&ownerDocument)
  62     , m_start(m_ownerDocument)
  63     , m_end(m_ownerDocument)
  64 {
  65 #ifndef NDEBUG
  66     rangeCounter.increment();
  67 #endif
  68
  69     m_ownerDocument->attachRange(this);
  70 }
  71
  72 PassRefPtrWillBeRawPtr<Range> Range::create(Document& ownerDocument)
  73 {
  74     return adoptRefWillBeNoop(new Range(ownerDocument));
  75 }
  76
  77 inline Range::Range(Document& ownerDocument, Node* startContainer, int startOffset, Node* endContainer, int endOffset)
  78     : m_ownerDocument(&ownerDocument)
  79     , m_start(m_ownerDocument)
  80     , m_end(m_ownerDocument)
  81 {
  82 #ifndef NDEBUG
  83     rangeCounter.increment();
  84 #endif
  85
  86     m_ownerDocument->attachRange(this);
  87
  88     // Simply setting the containers and offsets directly would not do any of the checking
  89     // that setStart and setEnd do, so we call those functions.
  90     setStart(startContainer, startOffset);
  91     setEnd(endContainer, endOffset);
  92 }
  93
  94 PassRefPtrWillBeRawPtr<Range> Range::create(Document& ownerDocument, Node* startContainer, int startOffset, Node* endContainer, int endOffset)
  95 {
  96     return adoptRefWillBeNoop(new Range(ownerDocument, startContainer, startOffset, endContainer, endOffset));
  97 }
  98
  99 PassRefPtrWillBeRawPtr<Range> Range::create(Document& ownerDocument, const Position& start, const Position& end)
 100 {
 101     return adoptRefWillBeNoop(new Range(ownerDocument, start.containerNode(), start.computeOffsetInContainerNode(), end.containerNode(), end.computeOffsetInContainerNode()));
 102 }
 103
 104 Range::~Range()
 105 {
 106 #if !ENABLE(OILPAN)
 107     // Always detach (even if we've already detached) to fix https://bugs.webkit.org/show_bug.cgi?id=26044
 108     m_ownerDocument->detachRange(this);
 109 #endif
 110
 111 #ifndef NDEBUG
 112     rangeCounter.decrement();
 113 #endif
 114 }
 115
 116 void Range::setDocument(Document& document)
 117 {
 118     ASSERT(m_ownerDocument != document);
 119     ASSERT(m_ownerDocument);
 120     m_ownerDocument->detachRange(this);
 121     m_ownerDocument = &document;
 122     m_start.setToStartOfNode(document);
 123     m_end.setToStartOfNode(document);
 124     m_ownerDocument->attachRange(this);
 125 }
 126
 127 Node* Range::commonAncestorContainer() const
 128 {
 129     return commonAncestorContainer(m_start.container(), m_end.container());
 130 }
 131
 132 Node* Range::commonAncestorContainer(Node* containerA, Node* containerB)
 133 {
 134     for (Node* parentA = containerA; parentA; parentA = parentA->parentNode()) {
 135         for (Node* parentB = containerB; parentB; parentB = parentB->parentNode()) {
 136             if (parentA == parentB)
 137                 return parentA;
 138         }
 139     }
 140     return 0;
 141 }
 142
 143 static inline bool checkForDifferentRootContainer(const RangeBoundaryPoint& start, const RangeBoundaryPoint& end)
 144 {
 145     Node* endRootContainer = end.container();
 146     while (endRootContainer->parentNode())
 147         endRootContainer = endRootContainer->parentNode();
 148     Node* startRootContainer = start.container();
 149     while (startRootContainer->parentNode())
 150         startRootContainer = startRootContainer->parentNode();
 151
 152     return startRootContainer != endRootContainer || (Range::compareBoundaryPoints(start, end, ASSERT_NO_EXCEPTION) > 0);
 153 }
 154
 155 void Range::setStart(PassRefPtrWillBeRawPtr<Node> refNode, int offset, ExceptionState& exceptionState)
 156 {
 157     if (!refNode) {
 158         exceptionState.throwDOMException(NotFoundError, "The node provided was null.");
 159         return;
 160     }
 161
 162     bool didMoveDocument = false;
 163     if (refNode->document() != m_ownerDocument) {
 164         setDocument(refNode->document());
 165         didMoveDocument = true;
 166     }
 167
 168     Node* childNode = checkNodeWOffset(refNode.get(), offset, exceptionState);
 169     if (exceptionState.hadException())
 170         return;
 171
 172     m_start.set(refNode, offset, childNode);
 173
 174     if (didMoveDocument || checkForDifferentRootContainer(m_start, m_end))
 175         collapse(true);
 176 }
 177
 178 void Range::setEnd(PassRefPtrWillBeRawPtr<Node> refNode, int offset, ExceptionState& exceptionState)
 179 {
 180     if (!refNode) {
 181         exceptionState.throwDOMException(NotFoundError, "The node provided was null.");
 182         return;
 183     }
 184
 185     bool didMoveDocument = false;
 186     if (refNode->document() != m_ownerDocument) {
 187         setDocument(refNode->document());
 188         didMoveDocument = true;
 189     }
 190
 191     Node* childNode = checkNodeWOffset(refNode.get(), offset, exceptionState);
 192     if (exceptionState.hadException())
 193         return;
 194
 195     m_end.set(refNode, offset, childNode);
 196
 197     if (didMoveDocument || checkForDifferentRootContainer(m_start, m_end))
 198         collapse(false);
 199 }
 200
 201 void Range::setStart(const Position& start, ExceptionState& exceptionState)
 202 {
 203     Position parentAnchored = start.parentAnchoredEquivalent();
 204     setStart(parentAnchored.containerNode(), parentAnchored.offsetInContainerNode(), exceptionState);
 205 }
 206
 207 void Range::setEnd(const Position& end, ExceptionState& exceptionState)
 208 {
 209     Position parentAnchored = end.parentAnchoredEquivalent();
 210     setEnd(parentAnchored.containerNode(), parentAnchored.offsetInContainerNode(), exceptionState);
 211 }
 212
 213 void Range::collapse(bool toStart)
 214 {
 215     if (toStart)
 216         m_end = m_start;
 217     else
 218         m_start = m_end;
 219 }
 220
 221 bool Range::isPointInRange(Node* refNode, int offset, ExceptionState& exceptionState)
 222 {
 223     if (!refNode) {
 224         exceptionState.throwDOMException(HierarchyRequestError, "The node provided was null.");
 225         return false;
 226     }
 227
 228     if (!refNode->inActiveDocument() || refNode->document() != m_ownerDocument) {
 229         return false;
 230     }
 231
 232     checkNodeWOffset(refNode, offset, exceptionState);
 233     if (exceptionState.hadException())
 234         return false;
 235
 236     return compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset(), exceptionState) >= 0 && !exceptionState.hadException()
 237         && compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset(), exceptionState) <= 0 && !exceptionState.hadException();
 238 }
 239
 240 short Range::comparePoint(Node* refNode, int offset, ExceptionState& exceptionState) const
 241 {
 242     // http://developer.mozilla.org/en/docs/DOM:range.comparePoint
 243     // This method returns -1, 0 or 1 depending on if the point described by the
 244     // refNode node and an offset within the node is before, same as, or after the range respectively.
 245
 246     if (!refNode->inActiveDocument()) {
 247         exceptionState.throwDOMException(WrongDocumentError, "The node provided is not in an active document.");
 248         return 0;
 249     }
 250
 251     if (refNode->document() != m_ownerDocument) {
 252         exceptionState.throwDOMException(WrongDocumentError, "The node provided is not in this Range's Document.");
 253         return 0;
 254     }
 255
 256     checkNodeWOffset(refNode, offset, exceptionState);
 257     if (exceptionState.hadException())
 258         return 0;
 259
 260     // compare to start, and point comes before
 261     if (compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset(), exceptionState) < 0)
 262         return -1;
 263
 264     if (exceptionState.hadException())
 265         return 0;
 266
 267     // compare to end, and point comes after
 268     if (compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset(), exceptionState) > 0 && !exceptionState.hadException())
 269         return 1;
 270
 271     // point is in the middle of this range, or on the boundary points
 272     return 0;
 273 }
 274
 275 Range::CompareResults Range::compareNode(Node* refNode, ExceptionState& exceptionState) const
 276 {
 277     // http://developer.mozilla.org/en/docs/DOM:range.compareNode
 278     // This method returns 0, 1, 2, or 3 based on if the node is before, after,
 279     // before and after(surrounds), or inside the range, respectively
 280
 281     if (!refNode) {
 282         exceptionState.throwDOMException(NotFoundError, "The node provided was null.");
 283         return NODE_BEFORE;
 284     }
 285
 286     if (!refNode->inActiveDocument()) {
 287         // Firefox doesn't throw an exception for this case; it returns 0.
 288         return NODE_BEFORE;
 289     }
 290
 291     if (refNode->document() != m_ownerDocument) {
 292         // Firefox doesn't throw an exception for this case; it returns 0.
 293         return NODE_BEFORE;
 294     }
 295
 296     ContainerNode* parentNode = refNode->parentNode();
 297     int nodeIndex = refNode->nodeIndex();
 298
 299     if (!parentNode) {
 300         // if the node is the top document we should return NODE_BEFORE_AND_AFTER
 301         // but we throw to match firefox behavior
 302         exceptionState.throwDOMException(NotFoundError, "The provided node has no parent.");
 303         return NODE_BEFORE;
 304     }
 305
 306     if (comparePoint(parentNode, nodeIndex, exceptionState) < 0) { // starts before
 307         if (comparePoint(parentNode, nodeIndex + 1, exceptionState) > 0) // ends after the range
 308             return NODE_BEFORE_AND_AFTER;
 309         return NODE_BEFORE; // ends before or in the range
 310     }
 311     // starts at or after the range start
 312     if (comparePoint(parentNode, nodeIndex + 1, exceptionState) > 0) // ends after the range
 313         return NODE_AFTER;
 314     return NODE_INSIDE; // ends inside the range
 315 }
 316
 317 short Range::compareBoundaryPoints(unsigned how, const Range* sourceRange, ExceptionState& exceptionState) const
 318 {
 319     if (!(how == START_TO_START || how == START_TO_END || how == END_TO_END || how == END_TO_START)) {
 320         exceptionState.throwDOMException(NotSupportedError, "The comparison method provided must be one of 'START_TO_START', 'START_TO_END', 'END_TO_END', or 'END_TO_START'.");
 321         return 0;
 322     }
 323
 324     Node* thisCont = commonAncestorContainer();
 325     Node* sourceCont = sourceRange->commonAncestorContainer();
 326     if (thisCont->document() != sourceCont->document()) {
 327         exceptionState.throwDOMException(WrongDocumentError, "The source range is in a different document than this range.");
 328         return 0;
 329     }
 330
 331     Node* thisTop = thisCont;
 332     Node* sourceTop = sourceCont;
 333     while (thisTop->parentNode())
 334         thisTop = thisTop->parentNode();
 335     while (sourceTop->parentNode())
 336         sourceTop = sourceTop->parentNode();
 337     if (thisTop != sourceTop) { // in different DocumentFragments
 338         exceptionState.throwDOMException(WrongDocumentError, "The source range is in a different document than this range.");
 339         return 0;
 340     }
 341
 342     switch (how) {
 343         case START_TO_START:
 344             return compareBoundaryPoints(m_start, sourceRange->m_start, exceptionState);
 345         case START_TO_END:
 346             return compareBoundaryPoints(m_end, sourceRange->m_start, exceptionState);
 347         case END_TO_END:
 348             return compareBoundaryPoints(m_end, sourceRange->m_end, exceptionState);
 349         case END_TO_START:
 350             return compareBoundaryPoints(m_start, sourceRange->m_end, exceptionState);
 351     }
 352
 353     ASSERT_NOT_REACHED();
 354     return 0;
 355 }
 356
 357 short Range::compareBoundaryPoints(Node* containerA, int offsetA, Node* containerB, int offsetB, ExceptionState& exceptionState)
 358 {
 359     ASSERT(containerA);
 360     ASSERT(containerB);
 361
 362     if (!containerA)
 363         return -1;
 364     if (!containerB)
 365         return 1;
 366
 367     // see DOM2 traversal & range section 2.5
 368
 369     // case 1: both points have the same container
 370     if (containerA == containerB) {
 371         if (offsetA == offsetB)
 372             return 0;           // A is equal to B
 373         if (offsetA < offsetB)
 374             return -1;          // A is before B
 375         else
 376             return 1;           // A is after B
 377     }
 378
 379     // case 2: node C (container B or an ancestor) is a child node of A
 380     Node* c = containerB;
 381     while (c && c->parentNode() != containerA)
 382         c = c->parentNode();
 383     if (c) {
 384         int offsetC = 0;
 385         Node* n = containerA->firstChild();
 386         while (n != c && offsetC < offsetA) {
 387             offsetC++;
 388             n = n->nextSibling();
 389         }
 390
 391         if (offsetA <= offsetC)
 392             return -1;              // A is before B
 393         else
 394             return 1;               // A is after B
 395     }
 396
 397     // case 3: node C (container A or an ancestor) is a child node of B
 398     c = containerA;
 399     while (c && c->parentNode() != containerB)
 400         c = c->parentNode();
 401     if (c) {
 402         int offsetC = 0;
 403         Node* n = containerB->firstChild();
 404         while (n != c && offsetC < offsetB) {
 405             offsetC++;
 406             n = n->nextSibling();
 407         }
 408
 409         if (offsetC < offsetB)
 410             return -1;              // A is before B
 411         else
 412             return 1;               // A is after B
 413     }
 414
 415     // case 4: containers A & B are siblings, or children of siblings
 416     // ### we need to do a traversal here instead
 417     Node* commonAncestor = commonAncestorContainer(containerA, containerB);
 418     if (!commonAncestor) {
 419         exceptionState.throwDOMException(WrongDocumentError, "The two ranges are in separate documents.");
 420         return 0;
 421     }
 422     Node* childA = containerA;
 423     while (childA && childA->parentNode() != commonAncestor)
 424         childA = childA->parentNode();
 425     if (!childA)
 426         childA = commonAncestor;
 427     Node* childB = containerB;
 428     while (childB && childB->parentNode() != commonAncestor)
 429         childB = childB->parentNode();
 430     if (!childB)
 431         childB = commonAncestor;
 432
 433     if (childA == childB)
 434         return 0; // A is equal to B
 435
 436     Node* n = commonAncestor->firstChild();
 437     while (n) {
 438         if (n == childA)
 439             return -1; // A is before B
 440         if (n == childB)
 441             return 1; // A is after B
 442         n = n->nextSibling();
 443     }
 444
 445     // Should never reach this point.
 446     ASSERT_NOT_REACHED();
 447     return 0;
 448 }
 449
 450 short Range::compareBoundaryPoints(const RangeBoundaryPoint& boundaryA, const RangeBoundaryPoint& boundaryB, ExceptionState& exceptionState)
 451 {
 452     return compareBoundaryPoints(boundaryA.container(), boundaryA.offset(), boundaryB.container(), boundaryB.offset(), exceptionState);
 453 }
 454
 455 bool Range::boundaryPointsValid() const
 456 {
 457     TrackExceptionState exceptionState;
 458     return compareBoundaryPoints(m_start, m_end, exceptionState) <= 0 && !exceptionState.hadException();
 459 }
 460
 461 void Range::deleteContents(ExceptionState& exceptionState)
 462 {
 463     ASSERT(boundaryPointsValid());
 464
 465     {
 466         EventQueueScope eventQueueScope;
 467         processContents(DELETE_CONTENTS, exceptionState);
 468     }
 469 }
 470
 471 static bool nodeValidForIntersects(Node* refNode, Document* expectedDocument, ExceptionState& exceptionState)
 472 {
 473     if (!refNode) {
 474         exceptionState.throwDOMException(NotFoundError, "The node provided is null.");
 475         return false;
 476     }
 477
 478     if (!refNode->inActiveDocument() || refNode->document() != expectedDocument) {
 479         // Firefox doesn't throw an exception for these cases; it returns false.
 480         return false;
 481     }
 482
 483     return true;
 484 }
 485
 486 bool Range::intersectsNode(Node* refNode, ExceptionState& exceptionState)
 487 {
 488     // http://developer.mozilla.org/en/docs/DOM:range.intersectsNode
 489     // Returns a bool if the node intersects the range.
 490     if (!nodeValidForIntersects(refNode, m_ownerDocument.get(), exceptionState))
 491         return false;
 492
 493     ContainerNode* parentNode = refNode->parentNode();
 494     int nodeIndex = refNode->nodeIndex();
 495
 496     if (!parentNode) {
 497         // if the node is the top document we should return NODE_BEFORE_AND_AFTER
 498         // but we throw to match firefox behavior
 499         exceptionState.throwDOMException(NotFoundError, "The node provided has no parent.");
 500         return false;
 501     }
 502
 503     if (comparePoint(parentNode, nodeIndex, exceptionState) < 0 // starts before start
 504         && comparePoint(parentNode, nodeIndex + 1, exceptionState) < 0) { // ends before start
 505         return false;
 506     }
 507
 508     if (comparePoint(parentNode, nodeIndex, exceptionState) > 0 // starts after end
 509         && comparePoint(parentNode, nodeIndex + 1, exceptionState) > 0) { // ends after end
 510         return false;
 511     }
 512
 513     return true; // all other cases
 514 }
 515
 516 bool Range::intersectsNode(Node* refNode, const Position& start, const Position& end, ExceptionState& exceptionState)
 517 {
 518     // http://developer.mozilla.org/en/docs/DOM:range.intersectsNode
 519     // Returns a bool if the node intersects the range.
 520     if (!nodeValidForIntersects(refNode, start.document(), exceptionState))
 521         return false;
 522
 523     ContainerNode* parentNode = refNode->parentNode();
 524     int nodeIndex = refNode->nodeIndex();
 525
 526     if (!parentNode) {
 527         // if the node is the top document we should return NODE_BEFORE_AND_AFTER
 528         // but we throw to match firefox behavior
 529         exceptionState.throwDOMException(NotFoundError, "The node provided has no parent.");
 530         return false;
 531     }
 532
 533     Node* startContainerNode = start.containerNode();
 534     int startOffset = start.computeOffsetInContainerNode();
 535
 536     if (compareBoundaryPoints(parentNode, nodeIndex, startContainerNode, startOffset, exceptionState) < 0 // starts before start
 537         && compareBoundaryPoints(parentNode, nodeIndex + 1, startContainerNode, startOffset, exceptionState) < 0) { // ends before start
 538         ASSERT(!exceptionState.hadException());
 539         return false;
 540     }
 541
 542     Node* endContainerNode = end.containerNode();
 543     int endOffset = end.computeOffsetInContainerNode();
 544
 545     if (compareBoundaryPoints(parentNode, nodeIndex, endContainerNode, endOffset, exceptionState) > 0 // starts after end
 546         && compareBoundaryPoints(parentNode, nodeIndex + 1, endContainerNode, endOffset, exceptionState) > 0) { // ends after end
 547         ASSERT(!exceptionState.hadException());
 548         return false;
 549     }
 550
 551     return true; // all other cases
 552 }
 553
 554 static inline Node* highestAncestorUnderCommonRoot(Node* node, Node* commonRoot)
 555 {
 556     if (node == commonRoot)
 557         return 0;
 558
 559     ASSERT(commonRoot->contains(node));
 560
 561     while (node->parentNode() != commonRoot)
 562         node = node->parentNode();
 563
 564     return node;
 565 }
 566
 567 static inline Node* childOfCommonRootBeforeOffset(Node* container, unsigned offset, Node* commonRoot)
 568 {
 569     ASSERT(container);
 570     ASSERT(commonRoot);
 571
 572     if (!commonRoot->contains(container))
 573         return 0;
 574
 575     if (container == commonRoot) {
 576         container = container->firstChild();
 577         for (unsigned i = 0; container && i < offset; i++)
 578             container = container->nextSibling();
 579     } else {
 580         while (container->parentNode() != commonRoot)
 581             container = container->parentNode();
 582     }
 583
 584     return container;
 585 }
 586
 587 PassRefPtrWillBeRawPtr<DocumentFragment> Range::processContents(ActionType action, ExceptionState& exceptionState)
 588 {
 589     typedef WillBeHeapVector<RefPtrWillBeMember<Node>> NodeVector;
 590
 591     RefPtrWillBeRawPtr<DocumentFragment> fragment = nullptr;
 592     if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)
 593         fragment = DocumentFragment::create(*m_ownerDocument.get());
 594
 595     if (collapsed())
 596         return fragment.release();
 597
 598     RefPtrWillBeRawPtr<Node> commonRoot = commonAncestorContainer();
 599     ASSERT(commonRoot);
 600
 601     if (m_start.container() == m_end.container()) {
 602         processContentsBetweenOffsets(action, fragment, m_start.container(), m_start.offset(), m_end.offset(), exceptionState);
 603         return fragment;
 604     }
 605
 606     // Since mutation observers can modify the range during the process, the boundary points need to be saved.
 607     RangeBoundaryPoint originalStart(m_start);
 608     RangeBoundaryPoint originalEnd(m_end);
 609
 610     // what is the highest node that partially selects the start / end of the range?
 611     RefPtrWillBeRawPtr<Node> partialStart = highestAncestorUnderCommonRoot(originalStart.container(), commonRoot.get());
 612     RefPtrWillBeRawPtr<Node> partialEnd = highestAncestorUnderCommonRoot(originalEnd.container(), commonRoot.get());
 613
 614     // Start and end containers are different.
 615     // There are three possibilities here:
 616     // 1. Start container == commonRoot (End container must be a descendant)
 617     // 2. End container == commonRoot (Start container must be a descendant)
 618     // 3. Neither is commonRoot, they are both descendants
 619     //
 620     // In case 3, we grab everything after the start (up until a direct child
 621     // of commonRoot) into leftContents, and everything before the end (up until
 622     // a direct child of commonRoot) into rightContents. Then we process all
 623     // commonRoot children between leftContents and rightContents
 624     //
 625     // In case 1 or 2, we skip either processing of leftContents or rightContents,
 626     // in which case the last lot of nodes either goes from the first or last
 627     // child of commonRoot.
 628     //
 629     // These are deleted, cloned, or extracted (i.e. both) depending on action.
 630
 631     // Note that we are verifying that our common root hierarchy is still intact
 632     // after any DOM mutation event, at various stages below. See webkit bug 60350.
 633
 634     RefPtrWillBeRawPtr<Node> leftContents = nullptr;
 635     if (originalStart.container() != commonRoot && commonRoot->contains(originalStart.container())) {
 636         leftContents = processContentsBetweenOffsets(action, nullptr, originalStart.container(), originalStart.offset(), originalStart.container()->lengthOfContents(), exceptionState);
 637         leftContents = processAncestorsAndTheirSiblings(action, originalStart.container(), ProcessContentsForward, leftContents, commonRoot.get(), exceptionState);
 638     }
 639
 640     RefPtrWillBeRawPtr<Node> rightContents = nullptr;
 641     if (m_end.container() != commonRoot && commonRoot->contains(originalEnd.container())) {
 642         rightContents = processContentsBetweenOffsets(action, nullptr, originalEnd.container(), 0, originalEnd.offset(), exceptionState);
 643         rightContents = processAncestorsAndTheirSiblings(action, originalEnd.container(), ProcessContentsBackward, rightContents, commonRoot.get(), exceptionState);
 644     }
 645
 646     // delete all children of commonRoot between the start and end container
 647     RefPtrWillBeRawPtr<Node> processStart = childOfCommonRootBeforeOffset(originalStart.container(), originalStart.offset(), commonRoot.get());
 648     if (processStart && originalStart.container() != commonRoot) // processStart contains nodes before m_start.
 649         processStart = processStart->nextSibling();
 650     RefPtrWillBeRawPtr<Node> processEnd = childOfCommonRootBeforeOffset(originalEnd.container(), originalEnd.offset(), commonRoot.get());
 651
 652     // Collapse the range, making sure that the result is not within a node that was partially selected.
 653     if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
 654         if (partialStart && commonRoot->contains(partialStart.get())) {
 655             // FIXME: We should not continue if we have an earlier error.
 656             exceptionState.clearException();
 657             setStart(partialStart->parentNode(), partialStart->nodeIndex() + 1, exceptionState);
 658         } else if (partialEnd && commonRoot->contains(partialEnd.get())) {
 659             // FIXME: We should not continue if we have an earlier error.
 660             exceptionState.clearException();
 661             setStart(partialEnd->parentNode(), partialEnd->nodeIndex(), exceptionState);
 662         }
 663         if (exceptionState.hadException())
 664             return nullptr;
 665         m_end = m_start;
 666     }
 667
 668     originalStart.clear();
 669     originalEnd.clear();
 670
 671     // Now add leftContents, stuff in between, and rightContents to the fragment
 672     // (or just delete the stuff in between)
 673
 674     if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && leftContents)
 675         fragment->appendChild(leftContents, exceptionState);
 676
 677     if (processStart) {
 678         NodeVector nodes;
 679         for (Node* n = processStart.get(); n && n != processEnd; n = n->nextSibling())
 680             nodes.append(n);
 681         processNodes(action, nodes, commonRoot, fragment, exceptionState);
 682     }
 683
 684     if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && rightContents)
 685         fragment->appendChild(rightContents, exceptionState);
 686
 687     return fragment.release();
 688 }
 689
 690 static inline void deleteCharacterData(PassRefPtrWillBeRawPtr<CharacterData> data, unsigned startOffset, unsigned endOffset, ExceptionState& exceptionState)
 691 {
 692     if (data->length() - endOffset)
 693         data->deleteData(endOffset, data->length() - endOffset, exceptionState);
 694     if (startOffset)
 695         data->deleteData(0, startOffset, exceptionState);
 696 }
 697
 698 PassRefPtrWillBeRawPtr<Node> Range::processContentsBetweenOffsets(ActionType action, PassRefPtrWillBeRawPtr<DocumentFragment> fragment,
 699     Node* container, unsigned startOffset, unsigned endOffset, ExceptionState& exceptionState)
 700 {
 701     ASSERT(container);
 702     ASSERT(startOffset <= endOffset);
 703
 704     // This switch statement must be consistent with that of Node::lengthOfContents.
 705     RefPtrWillBeRawPtr<Node> result = nullptr;
 706     switch (container->nodeType()) {
 707     case Node::TEXT_NODE:
 708     case Node::CDATA_SECTION_NODE:
 709     case Node::COMMENT_NODE:
 710         endOffset = std::min(endOffset, toCharacterData(container)->length());
 711         if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 712             RefPtrWillBeRawPtr<CharacterData> c = static_pointer_cast<CharacterData>(container->cloneNode(true));
 713             deleteCharacterData(c, startOffset, endOffset, exceptionState);
 714             if (fragment) {
 715                 result = fragment;
 716                 result->appendChild(c.release(), exceptionState);
 717             } else
 718                 result = c.release();
 719         }
 720         if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS)
 721             toCharacterData(container)->deleteData(startOffset, endOffset - startOffset, exceptionState);
 722         break;
 723     case Node::PROCESSING_INSTRUCTION_NODE:
 724         endOffset = std::min(endOffset, toProcessingInstruction(container)->data().length());
 725         if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 726             RefPtrWillBeRawPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(container->cloneNode(true));
 727             c->setData(c->data().substring(startOffset, endOffset - startOffset));
 728             if (fragment) {
 729                 result = fragment;
 730                 result->appendChild(c.release(), exceptionState);
 731             } else
 732                 result = c.release();
 733         }
 734         if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
 735             ProcessingInstruction* pi = toProcessingInstruction(container);
 736             String data(pi->data());
 737             data.remove(startOffset, endOffset - startOffset);
 738             pi->setData(data);
 739         }
 740         break;
 741     case Node::ELEMENT_NODE:
 742     case Node::ATTRIBUTE_NODE:
 743     case Node::DOCUMENT_NODE:
 744     case Node::DOCUMENT_TYPE_NODE:
 745     case Node::DOCUMENT_FRAGMENT_NODE:
 746         // FIXME: Should we assert that some nodes never appear here?
 747         if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 748             if (fragment)
 749                 result = fragment;
 750             else
 751                 result = container->cloneNode(false);
 752         }
 753
 754         Node* n = container->firstChild();
 755         WillBeHeapVector<RefPtrWillBeMember<Node>> nodes;
 756         for (unsigned i = startOffset; n && i; i--)
 757             n = n->nextSibling();
 758         for (unsigned i = startOffset; n && i < endOffset; i++, n = n->nextSibling())
 759             nodes.append(n);
 760
 761         processNodes(action, nodes, container, result, exceptionState);
 762         break;
 763     }
 764
 765     return result.release();
 766 }
 767
 768 void Range::processNodes(ActionType action, WillBeHeapVector<RefPtrWillBeMember<Node>>& nodes, PassRefPtrWillBeRawPtr<Node> oldContainer, PassRefPtrWillBeRawPtr<Node> newContainer, ExceptionState& exceptionState)
 769 {
 770     for (auto& node : nodes) {
 771         switch (action) {
 772         case DELETE_CONTENTS:
 773             oldContainer->removeChild(node.get(), exceptionState);
 774             break;
 775         case EXTRACT_CONTENTS:
 776             newContainer->appendChild(node.release(), exceptionState); // Will remove n from its parent.
 777             break;
 778         case CLONE_CONTENTS:
 779             newContainer->appendChild(node->cloneNode(true), exceptionState);
 780             break;
 781         }
 782     }
 783 }
 784
 785 PassRefPtrWillBeRawPtr<Node> Range::processAncestorsAndTheirSiblings(ActionType action, Node* container, ContentsProcessDirection direction, PassRefPtrWillBeRawPtr<Node> passedClonedContainer, Node* commonRoot, ExceptionState& exceptionState)
 786 {
 787     typedef WillBeHeapVector<RefPtrWillBeMember<Node>> NodeVector;
 788
 789     RefPtrWillBeRawPtr<Node> clonedContainer = passedClonedContainer;
 790     NodeVector ancestors;
 791     for (ContainerNode* n = container->parentNode(); n && n != commonRoot; n = n->parentNode())
 792         ancestors.append(n);
 793
 794     RefPtrWillBeRawPtr<Node> firstChildInAncestorToProcess = direction == ProcessContentsForward ? container->nextSibling() : container->previousSibling();
 795     for (const RefPtrWillBeRawPtr<Node>& ancestor : ancestors) {
 796         if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 797             if (RefPtrWillBeRawPtr<Node> clonedAncestor = ancestor->cloneNode(false)) { // Might have been removed already during mutation event.
 798                 clonedAncestor->appendChild(clonedContainer, exceptionState);
 799                 clonedContainer = clonedAncestor;
 800             }
 801         }
 802
 803         // Copy siblings of an ancestor of start/end containers
 804         // FIXME: This assertion may fail if DOM is modified during mutation event
 805         // FIXME: Share code with Range::processNodes
 806         ASSERT(!firstChildInAncestorToProcess || firstChildInAncestorToProcess->parentNode() == ancestor);
 807
 808         NodeVector nodes;
 809         for (Node* child = firstChildInAncestorToProcess.get(); child;
 810             child = (direction == ProcessContentsForward) ? child->nextSibling() : child->previousSibling())
 811             nodes.append(child);
 812
 813         for (const RefPtrWillBeRawPtr<Node>& node : nodes) {
 814             Node* child = node.get();
 815             switch (action) {
 816             case DELETE_CONTENTS:
 817                 // Prior call of ancestor->removeChild() may cause a tree change due to DOMSubtreeModified event.
 818                 // Therefore, we need to make sure |ancestor| is still |child|'s parent.
 819                 if (ancestor == child->parentNode())
 820                     ancestor->removeChild(child, exceptionState);
 821                 break;
 822             case EXTRACT_CONTENTS: // will remove child from ancestor
 823                 if (direction == ProcessContentsForward)
 824                     clonedContainer->appendChild(child, exceptionState);
 825                 else
 826                     clonedContainer->insertBefore(child, clonedContainer->firstChild(), exceptionState);
 827                 break;
 828             case CLONE_CONTENTS:
 829                 if (direction == ProcessContentsForward)
 830                     clonedContainer->appendChild(child->cloneNode(true), exceptionState);
 831                 else
 832                     clonedContainer->insertBefore(child->cloneNode(true), clonedContainer->firstChild(), exceptionState);
 833                 break;
 834             }
 835         }
 836         firstChildInAncestorToProcess = direction == ProcessContentsForward ? ancestor->nextSibling() : ancestor->previousSibling();
 837     }
 838
 839     return clonedContainer.release();
 840 }
 841
 842 PassRefPtrWillBeRawPtr<DocumentFragment> Range::extractContents(ExceptionState& exceptionState)
 843 {
 844     checkExtractPrecondition(exceptionState);
 845     if (exceptionState.hadException())
 846         return nullptr;
 847
 848     return processContents(EXTRACT_CONTENTS, exceptionState);
 849 }
 850
 851 PassRefPtrWillBeRawPtr<DocumentFragment> Range::cloneContents(ExceptionState& exceptionState)
 852 {
 853     return processContents(CLONE_CONTENTS, exceptionState);
 854 }
 855
 856 void Range::insertNode(PassRefPtrWillBeRawPtr<Node> prpNewNode, ExceptionState& exceptionState)
 857 {
 858     RefPtrWillBeRawPtr<Node> newNode = prpNewNode;
 859
 860     if (!newNode) {
 861         exceptionState.throwDOMException(NotFoundError, "The node provided is null.");
 862         return;
 863     }
 864
 865     // HierarchyRequestError: Raised if the container of the start of the Range is of a type that
 866     // does not allow children of the type of newNode or if newNode is an ancestor of the container.
 867
 868     // an extra one here - if a text node is going to split, it must have a parent to insert into
 869     bool startIsText = m_start.container()->isTextNode();
 870     if (startIsText && !m_start.container()->parentNode()) {
 871         exceptionState.throwDOMException(HierarchyRequestError, "This operation would split a text node, but there's no parent into which to insert.");
 872         return;
 873     }
 874
 875     // In the case where the container is a text node, we check against the container's parent, because
 876     // text nodes get split up upon insertion.
 877     Node* checkAgainst;
 878     if (startIsText)
 879         checkAgainst = m_start.container()->parentNode();
 880     else
 881         checkAgainst = m_start.container();
 882
 883     Node::NodeType newNodeType = newNode->nodeType();
 884     int numNewChildren;
 885     if (newNodeType == Node::DOCUMENT_FRAGMENT_NODE && !newNode->isShadowRoot()) {
 886         // check each child node, not the DocumentFragment itself
 887         numNewChildren = 0;
 888         for (Node* c = toDocumentFragment(newNode)->firstChild(); c; c = c->nextSibling()) {
 889             if (!checkAgainst->childTypeAllowed(c->nodeType())) {
 890                 exceptionState.throwDOMException(HierarchyRequestError, "The node to be inserted contains a '" + c->nodeName() + "' node, which may not be inserted here.");
 891                 return;
 892             }
 893             ++numNewChildren;
 894         }
 895     } else {
 896         numNewChildren = 1;
 897         if (!checkAgainst->childTypeAllowed(newNodeType)) {
 898             exceptionState.throwDOMException(HierarchyRequestError, "The node to be inserted is a '" + newNode->nodeName() + "' node, which may not be inserted here.");
 899             return;
 900         }
 901     }
 902
 903     for (Node* n = m_start.container(); n; n = n->parentNode()) {
 904         if (n == newNode) {
 905             exceptionState.throwDOMException(HierarchyRequestError, "The node to be inserted contains the insertion point; it may not be inserted into itself.");
 906             return;
 907         }
 908     }
 909
 910     // InvalidNodeTypeError: Raised if newNode is an Attr, Entity, Notation, ShadowRoot or Document node.
 911     switch (newNodeType) {
 912     case Node::ATTRIBUTE_NODE:
 913     case Node::DOCUMENT_NODE:
 914         exceptionState.throwDOMException(InvalidNodeTypeError, "The node to be inserted is a '" + newNode->nodeName() + "' node, which may not be inserted here.");
 915         return;
 916     default:
 917         if (newNode->isShadowRoot()) {
 918             exceptionState.throwDOMException(InvalidNodeTypeError, "The node to be inserted is a shadow root, which may not be inserted here.");
 919             return;
 920         }
 921         break;
 922     }
 923
 924     EventQueueScope scope;
 925     bool collapsed = m_start == m_end;
 926     RefPtrWillBeRawPtr<Node> container = nullptr;
 927     if (startIsText) {
 928         container = m_start.container();
 929         RefPtrWillBeRawPtr<Text> newText = toText(container)->splitText(m_start.offset(), exceptionState);
 930         if (exceptionState.hadException())
 931             return;
 932
 933         container = m_start.container();
 934         container->parentNode()->insertBefore(newNode.release(), newText.get(), exceptionState);
 935         if (exceptionState.hadException())
 936             return;
 937
 938         if (collapsed) {
 939             // The load event would be fired regardless of EventQueueScope;
 940             // e.g. by ContainerNode::updateTreeAfterInsertion
 941             // Given circumstance may mutate the tree so newText->parentNode() may become null
 942             if (!newText->parentNode()) {
 943                 exceptionState.throwDOMException(HierarchyRequestError, "This operation would set range's end to parent with new offset, but there's no parent into which to continue.");
 944                 return;
 945             }
 946             m_end.setToBeforeChild(*newText);
 947         }
 948     } else {
 949         RefPtrWillBeRawPtr<Node> lastChild = (newNodeType == Node::DOCUMENT_FRAGMENT_NODE) ? toDocumentFragment(newNode)->lastChild() : newNode.get();
 950         if (lastChild && lastChild == m_start.childBefore()) {
 951             // The insertion will do nothing, but we need to extend the range to include
 952             // the inserted nodes.
 953             Node* firstChild = (newNodeType == Node::DOCUMENT_FRAGMENT_NODE) ? toDocumentFragment(newNode)->firstChild() : newNode.get();
 954             ASSERT(firstChild);
 955             m_start.setToBeforeChild(*firstChild);
 956             return;
 957         }
 958
 959         container = m_start.container();
 960         container->insertBefore(newNode.release(), NodeTraversal::childAt(*container, m_start.offset()), exceptionState);
 961         if (exceptionState.hadException())
 962             return;
 963
 964         // Note that m_start.offset() may have changed as a result of container->insertBefore,
 965         // when the node we are inserting comes before the range in the same container.
 966         if (collapsed && numNewChildren)
 967             m_end.set(m_start.container(), m_start.offset() + numNewChildren, lastChild.get());
 968     }
 969 }
 970
 971 String Range::toString() const
 972 {
 973     StringBuilder builder;
 974
 975     Node* pastLast = pastLastNode();
 976     for (Node* n = firstNode(); n != pastLast; n = NodeTraversal::next(*n)) {
 977         Node::NodeType type = n->nodeType();
 978         if (type == Node::TEXT_NODE || type == Node::CDATA_SECTION_NODE) {
 979             String data = toCharacterData(n)->data();
 980             int length = data.length();
 981             int start = (n == m_start.container()) ? std::min(std::max(0, m_start.offset()), length) : 0;
 982             int end = (n == m_end.container()) ? std::min(std::max(start, m_end.offset()), length) : length;
 983             builder.append(data, start, end - start);
 984         }
 985     }
 986
 987     return builder.toString();
 988 }
 989
 990 String Range::toHTML() const
 991 {
 992     return createMarkup(this);
 993 }
 994
 995 String Range::text() const
 996 {
 997     return plainText(this, TextIteratorEmitsObjectReplacementCharacter);
 998 }
 999
1000 PassRefPtrWillBeRawPtr<DocumentFragment> Range::createContextualFragment(const String& markup, ExceptionState& exceptionState)
1001 {
1002     // Algorithm: http://domparsing.spec.whatwg.org/#extensions-to-the-range-interface
1003
1004     Node* node = m_start.container();
1005
1006     // Step 1.
1007     RefPtrWillBeRawPtr<Element> element;
1008     if (!m_start.offset() && (node->isDocumentNode() || node->isDocumentFragment()))
1009         element = nullptr;
1010     else if (node->isElementNode())
1011         element = toElement(node);
1012     else
1013         element = node->parentElement();
1014
1015     // Step 2.
1016     if (!element || isHTMLHtmlElement(element)) {
1017         Document& document = node->document();
1018
1019         if (document.isHTMLDocument() || document.isXHTMLDocument()) {
1020             // Optimization over spec: try to reuse the existing <body> element, if it is available.
1021             element = document.body();
1022             if (!element)
1023                 element = HTMLBodyElement::create(document);
1024         } else if (document.isSVGDocument()) {
1025             element = document.documentElement();
1026             if (!element)
1027                 element = SVGSVGElement::create(document);
1028         }
1029     }
1030
1031     if (!element || (!element->isHTMLElement() && !element->isSVGElement())) {
1032         exceptionState.throwDOMException(NotSupportedError, "The range's container must be an HTML or SVG Element, Document, or DocumentFragment.");
1033         return nullptr;
1034     }
1035
1036     // Steps 3, 4, 5.
1037     RefPtrWillBeRawPtr<DocumentFragment> fragment = blink::createContextualFragment(markup, element.get(), AllowScriptingContentAndDoNotMarkAlreadyStarted, exceptionState);
1038     if (!fragment)
1039         return nullptr;
1040
1041     return fragment.release();
1042 }
1043
1044
1045 void Range::detach()
1046 {
1047     // This is now a no-op as per the DOM specification.
1048 }
1049
1050 Node* Range::checkNodeWOffset(Node* n, int offset, ExceptionState& exceptionState) const
1051 {
1052     switch (n->nodeType()) {
1053         case Node::DOCUMENT_TYPE_NODE:
1054             exceptionState.throwDOMException(InvalidNodeTypeError, "The node provided is of type '" + n->nodeName() + "'.");
1055             return nullptr;
1056         case Node::CDATA_SECTION_NODE:
1057         case Node::COMMENT_NODE:
1058         case Node::TEXT_NODE:
1059             if (static_cast<unsigned>(offset) > toCharacterData(n)->length())
1060                 exceptionState.throwDOMException(IndexSizeError, "The offset " + String::number(offset) + " is larger than or equal to the node's length (" + String::number(toCharacterData(n)->length()) + ").");
1061             return nullptr;
1062         case Node::PROCESSING_INSTRUCTION_NODE:
1063             if (static_cast<unsigned>(offset) > toProcessingInstruction(n)->data().length())
1064                 exceptionState.throwDOMException(IndexSizeError, "The offset " + String::number(offset) + " is larger than or equal to than the node's length (" + String::number(toProcessingInstruction(n)->data().length()) + ").");
1065             return nullptr;
1066         case Node::ATTRIBUTE_NODE:
1067         case Node::DOCUMENT_FRAGMENT_NODE:
1068         case Node::DOCUMENT_NODE:
1069         case Node::ELEMENT_NODE: {
1070             if (!offset)
1071                 return nullptr;
1072             Node* childBefore = NodeTraversal::childAt(*n, offset - 1);
1073             if (!childBefore)
1074                 exceptionState.throwDOMException(IndexSizeError, "There is no child at offset " + String::number(offset) + ".");
1075             return childBefore;
1076         }
1077     }
1078     ASSERT_NOT_REACHED();
1079     return nullptr;
1080 }
1081
1082 void Range::checkNodeBA(Node* n, ExceptionState& exceptionState) const
1083 {
1084     if (!n) {
1085         exceptionState.throwDOMException(NotFoundError, "The node provided is null.");
1086         return;
1087     }
1088
1089     // InvalidNodeTypeError: Raised if the root container of refNode is not an
1090     // Attr, Document, DocumentFragment or ShadowRoot node, or part of a SVG shadow DOM tree,
1091     // or if refNode is a Document, DocumentFragment, ShadowRoot, Attr, Entity, or Notation node.
1092
1093     if (!n->parentNode()) {
1094         exceptionState.throwDOMException(InvalidNodeTypeError, "the given Node has no parent.");
1095         return;
1096     }
1097
1098     switch (n->nodeType()) {
1099         case Node::ATTRIBUTE_NODE:
1100         case Node::DOCUMENT_FRAGMENT_NODE:
1101         case Node::DOCUMENT_NODE:
1102             exceptionState.throwDOMException(InvalidNodeTypeError, "The node provided is of type '" + n->nodeName() + "'.");
1103             return;
1104         case Node::CDATA_SECTION_NODE:
1105         case Node::COMMENT_NODE:
1106         case Node::DOCUMENT_TYPE_NODE:
1107         case Node::ELEMENT_NODE:
1108         case Node::PROCESSING_INSTRUCTION_NODE:
1109         case Node::TEXT_NODE:
1110             break;
1111     }
1112
1113     Node* root = n;
1114     while (ContainerNode* parent = root->parentNode())
1115         root = parent;
1116
1117     switch (root->nodeType()) {
1118         case Node::ATTRIBUTE_NODE:
1119         case Node::DOCUMENT_NODE:
1120         case Node::DOCUMENT_FRAGMENT_NODE:
1121         case Node::ELEMENT_NODE:
1122             break;
1123         case Node::CDATA_SECTION_NODE:
1124         case Node::COMMENT_NODE:
1125         case Node::DOCUMENT_TYPE_NODE:
1126         case Node::PROCESSING_INSTRUCTION_NODE:
1127         case Node::TEXT_NODE:
1128             exceptionState.throwDOMException(InvalidNodeTypeError, "The node provided is of type '" + n->nodeName() + "'.");
1129             return;
1130     }
1131 }
1132
1133 PassRefPtrWillBeRawPtr<Range> Range::cloneRange() const
1134 {
1135     return Range::create(*m_ownerDocument.get(), m_start.container(), m_start.offset(), m_end.container(), m_end.offset());
1136 }
1137
1138 void Range::setStartAfter(Node* refNode, ExceptionState& exceptionState)
1139 {
1140     checkNodeBA(refNode, exceptionState);
1141     if (exceptionState.hadException())
1142         return;
1143
1144     setStart(refNode->parentNode(), refNode->nodeIndex() + 1, exceptionState);
1145 }
1146
1147 void Range::setEndBefore(Node* refNode, ExceptionState& exceptionState)
1148 {
1149     checkNodeBA(refNode, exceptionState);
1150     if (exceptionState.hadException())
1151         return;
1152
1153     setEnd(refNode->parentNode(), refNode->nodeIndex(), exceptionState);
1154 }
1155
1156 void Range::setEndAfter(Node* refNode, ExceptionState& exceptionState)
1157 {
1158     checkNodeBA(refNode, exceptionState);
1159     if (exceptionState.hadException())
1160         return;
1161
1162     setEnd(refNode->parentNode(), refNode->nodeIndex() + 1, exceptionState);
1163 }
1164
1165 void Range::selectNode(Node* refNode, ExceptionState& exceptionState)
1166 {
1167     if (!refNode) {
1168         exceptionState.throwDOMException(NotFoundError, "The node provided is null.");
1169         return;
1170     }
1171
1172     if (!refNode->parentNode()) {
1173         exceptionState.throwDOMException(InvalidNodeTypeError, "the given Node has no parent.");
1174         return;
1175     }
1176
1177     // InvalidNodeTypeError: Raised if an ancestor of refNode is an Entity, Notation or
1178     // DocumentType node or if refNode is a Document, DocumentFragment, ShadowRoot, Attr, Entity, or Notation
1179     // node.
1180     for (ContainerNode* anc = refNode->parentNode(); anc; anc = anc->parentNode()) {
1181         switch (anc->nodeType()) {
1182             case Node::ATTRIBUTE_NODE:
1183             case Node::CDATA_SECTION_NODE:
1184             case Node::COMMENT_NODE:
1185             case Node::DOCUMENT_FRAGMENT_NODE:
1186             case Node::DOCUMENT_NODE:
1187             case Node::ELEMENT_NODE:
1188             case Node::PROCESSING_INSTRUCTION_NODE:
1189             case Node::TEXT_NODE:
1190                 break;
1191             case Node::DOCUMENT_TYPE_NODE:
1192                 exceptionState.throwDOMException(InvalidNodeTypeError, "The node provided has an ancestor of type '" + anc->nodeName() + "'.");
1193                 return;
1194         }
1195     }
1196
1197     switch (refNode->nodeType()) {
1198         case Node::CDATA_SECTION_NODE:
1199         case Node::COMMENT_NODE:
1200         case Node::DOCUMENT_TYPE_NODE:
1201         case Node::ELEMENT_NODE:
1202         case Node::PROCESSING_INSTRUCTION_NODE:
1203         case Node::TEXT_NODE:
1204             break;
1205         case Node::ATTRIBUTE_NODE:
1206         case Node::DOCUMENT_FRAGMENT_NODE:
1207         case Node::DOCUMENT_NODE:
1208             exceptionState.throwDOMException(InvalidNodeTypeError, "The node provided is of type '" + refNode->nodeName() + "'.");
1209             return;
1210     }
1211
1212     if (m_ownerDocument != refNode->document())
1213         setDocument(refNode->document());
1214
1215     setStartBefore(refNode);
1216     setEndAfter(refNode);
1217 }
1218
1219 void Range::selectNodeContents(Node* refNode, ExceptionState& exceptionState)
1220 {
1221     if (!refNode) {
1222         exceptionState.throwDOMException(NotFoundError, "The node provided is null.");
1223         return;
1224     }
1225
1226     // InvalidNodeTypeError: Raised if refNode or an ancestor of refNode is an Entity, Notation
1227     // or DocumentType node.
1228     for (Node* n = refNode; n; n = n->parentNode()) {
1229         switch (n->nodeType()) {
1230         case Node::ATTRIBUTE_NODE:
1231         case Node::CDATA_SECTION_NODE:
1232         case Node::COMMENT_NODE:
1233         case Node::DOCUMENT_FRAGMENT_NODE:
1234         case Node::DOCUMENT_NODE:
1235         case Node::ELEMENT_NODE:
1236         case Node::PROCESSING_INSTRUCTION_NODE:
1237         case Node::TEXT_NODE:
1238             break;
1239         case Node::DOCUMENT_TYPE_NODE:
1240             exceptionState.throwDOMException(InvalidNodeTypeError, "The node provided is of type '" + refNode->nodeName() + "'.");
1241             return;
1242         }
1243     }
1244
1245     if (m_ownerDocument != refNode->document())
1246         setDocument(refNode->document());
1247
1248     m_start.setToStartOfNode(*refNode);
1249     m_end.setToEndOfNode(*refNode);
1250 }
1251
1252 bool Range::selectNodeContents(Node* refNode, Position& start, Position& end)
1253 {
1254     if (!refNode) {
1255         return false;
1256     }
1257
1258     for (Node* n = refNode; n; n = n->parentNode()) {
1259         switch (n->nodeType()) {
1260         case Node::ATTRIBUTE_NODE:
1261         case Node::CDATA_SECTION_NODE:
1262         case Node::COMMENT_NODE:
1263         case Node::DOCUMENT_FRAGMENT_NODE:
1264         case Node::DOCUMENT_NODE:
1265         case Node::ELEMENT_NODE:
1266         case Node::PROCESSING_INSTRUCTION_NODE:
1267         case Node::TEXT_NODE:
1268             break;
1269         case Node::DOCUMENT_TYPE_NODE:
1270             return false;
1271         }
1272     }
1273
1274     RangeBoundaryPoint startBoundaryPoint(refNode);
1275     startBoundaryPoint.setToStartOfNode(*refNode);
1276     start = startBoundaryPoint.toPosition();
1277     RangeBoundaryPoint endBoundaryPoint(refNode);
1278     endBoundaryPoint.setToEndOfNode(*refNode);
1279     end = endBoundaryPoint.toPosition();
1280     return true;
1281 }
1282
1283 void Range::surroundContents(PassRefPtrWillBeRawPtr<Node> passNewParent, ExceptionState& exceptionState)
1284 {
1285     RefPtrWillBeRawPtr<Node> newParent = passNewParent;
1286     if (!newParent) {
1287         exceptionState.throwDOMException(NotFoundError, "The node provided is null.");
1288         return;
1289     }
1290
1291     // InvalidStateError: Raised if the Range partially selects a non-Text node.
1292     Node* startNonTextContainer = m_start.container();
1293     if (startNonTextContainer->nodeType() == Node::TEXT_NODE)
1294         startNonTextContainer = startNonTextContainer->parentNode();
1295     Node* endNonTextContainer = m_end.container();
1296     if (endNonTextContainer->nodeType() == Node::TEXT_NODE)
1297         endNonTextContainer = endNonTextContainer->parentNode();
1298     if (startNonTextContainer != endNonTextContainer) {
1299         exceptionState.throwDOMException(InvalidStateError, "The Range has partially selected a non-Text node.");
1300         return;
1301     }
1302
1303     // InvalidNodeTypeError: Raised if node is an Attr, Entity, DocumentType, Notation,
1304     // Document, or DocumentFragment node.
1305     switch (newParent->nodeType()) {
1306         case Node::ATTRIBUTE_NODE:
1307         case Node::DOCUMENT_FRAGMENT_NODE:
1308         case Node::DOCUMENT_NODE:
1309         case Node::DOCUMENT_TYPE_NODE:
1310             exceptionState.throwDOMException(InvalidNodeTypeError, "The node provided is of type '" + newParent->nodeName() + "'.");
1311             return;
1312         case Node::CDATA_SECTION_NODE:
1313         case Node::COMMENT_NODE:
1314         case Node::ELEMENT_NODE:
1315         case Node::PROCESSING_INSTRUCTION_NODE:
1316         case Node::TEXT_NODE:
1317             break;
1318     }
1319
1320     // Raise a HierarchyRequestError if m_start.container() doesn't accept children like newParent.
1321     Node* parentOfNewParent = m_start.container();
1322
1323     // If m_start.container() is a character data node, it will be split and it will be its parent that will
1324     // need to accept newParent (or in the case of a comment, it logically "would" be inserted into the parent,
1325     // although this will fail below for another reason).
1326     if (parentOfNewParent->isCharacterDataNode())
1327         parentOfNewParent = parentOfNewParent->parentNode();
1328
1329     if (!parentOfNewParent) {
1330         exceptionState.throwDOMException(HierarchyRequestError, "The container node is a detached character data node; no parent node is available for insertion.");
1331         return;
1332     }
1333
1334     if (!parentOfNewParent->childTypeAllowed(newParent->nodeType())) {
1335         exceptionState.throwDOMException(HierarchyRequestError, "The node provided is of type '" + newParent->nodeName() + "', which may not be inserted here.");
1336         return;
1337     }
1338
1339     if (newParent->contains(m_start.container())) {
1340         exceptionState.throwDOMException(HierarchyRequestError, "The node provided contains the insertion point; it may not be inserted into itself.");
1341         return;
1342     }
1343
1344     // FIXME: Do we need a check if the node would end up with a child node of a type not
1345     // allowed by the type of node?
1346
1347     while (Node* n = newParent->firstChild()) {
1348         toContainerNode(newParent)->removeChild(n, exceptionState);
1349         if (exceptionState.hadException())
1350             return;
1351     }
1352     RefPtrWillBeRawPtr<DocumentFragment> fragment = extractContents(exceptionState);
1353     if (exceptionState.hadException())
1354         return;
1355     insertNode(newParent, exceptionState);
1356     if (exceptionState.hadException())
1357         return;
1358     newParent->appendChild(fragment.release(), exceptionState);
1359     if (exceptionState.hadException())
1360         return;
1361     selectNode(newParent.get(), exceptionState);
1362 }
1363
1364 void Range::setStartBefore(Node* refNode, ExceptionState& exceptionState)
1365 {
1366     checkNodeBA(refNode, exceptionState);
1367     if (exceptionState.hadException())
1368         return;
1369
1370     setStart(refNode->parentNode(), refNode->nodeIndex(), exceptionState);
1371 }
1372
1373 void Range::checkExtractPrecondition(ExceptionState& exceptionState)
1374 {
1375     ASSERT(boundaryPointsValid());
1376
1377     if (!commonAncestorContainer())
1378         return;
1379
1380     Node* pastLast = pastLastNode();
1381     for (Node* n = firstNode(); n != pastLast; n = NodeTraversal::next(*n)) {
1382         if (n->isDocumentTypeNode()) {
1383             exceptionState.throwDOMException(HierarchyRequestError, "The Range contains a doctype node.");
1384             return;
1385         }
1386     }
1387 }
1388
1389 Node* Range::firstNode() const
1390 {
1391     if (m_start.container()->offsetInCharacters())
1392         return m_start.container();
1393     if (Node* child = NodeTraversal::childAt(*m_start.container(), m_start.offset()))
1394         return child;
1395     if (!m_start.offset())
1396         return m_start.container();
1397     return NodeTraversal::nextSkippingChildren(*m_start.container());
1398 }
1399
1400 ShadowRoot* Range::shadowRoot() const
1401 {
1402     return startContainer() ? startContainer()->containingShadowRoot() : nullptr;
1403 }
1404
1405 Node* Range::pastLastNode() const
1406 {
1407     if (m_end.container()->offsetInCharacters())
1408         return NodeTraversal::nextSkippingChildren(*m_end.container());
1409     if (Node* child = NodeTraversal::childAt(*m_end.container(), m_end.offset()))
1410         return child;
1411     return NodeTraversal::nextSkippingChildren(*m_end.container());
1412 }
1413
1414 IntRect Range::boundingBox() const
1415 {
1416     IntRect result;
1417     Vector<IntRect> rects;
1418     textRects(rects);
1419     for (const IntRect& rect : rects)
1420         result.unite(rect);
1421     return result;
1422 }
1423
1424 void Range::textRects(Vector<IntRect>& rects, bool useSelectionHeight, RangeInFixedPosition* inFixed) const
1425 {
1426     Node* startContainer = m_start.container();
1427     ASSERT(startContainer);
1428     Node* endContainer = m_end.container();
1429     ASSERT(endContainer);
1430
1431     bool allFixed = true;
1432     bool someFixed = false;
1433
1434     Node* stopNode = pastLastNode();
1435     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(*node)) {
1436         RenderObject* r = node->renderer();
1437         if (!r || !r->isText())
1438             continue;
1439         RenderText* renderText = toRenderText(r);
1440         int startOffset = node == startContainer ? m_start.offset() : 0;
1441         int endOffset = node == endContainer ? m_end.offset() : std::numeric_limits<int>::max();
1442         bool isFixed = false;
1443         renderText->absoluteRectsForRange(rects, startOffset, endOffset, useSelectionHeight, &isFixed);
1444         allFixed &= isFixed;
1445         someFixed |= isFixed;
1446     }
1447
1448     if (inFixed)
1449         *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition);
1450 }
1451
1452 void Range::textQuads(Vector<FloatQuad>& quads, bool useSelectionHeight, RangeInFixedPosition* inFixed) const
1453 {
1454     Node* startContainer = m_start.container();
1455     ASSERT(startContainer);
1456     Node* endContainer = m_end.container();
1457     ASSERT(endContainer);
1458
1459     bool allFixed = true;
1460     bool someFixed = false;
1461
1462     Node* stopNode = pastLastNode();
1463     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(*node)) {
1464         RenderObject* r = node->renderer();
1465         if (!r || !r->isText())
1466             continue;
1467         RenderText* renderText = toRenderText(r);
1468         int startOffset = node == startContainer ? m_start.offset() : 0;
1469         int endOffset = node == endContainer ? m_end.offset() : std::numeric_limits<int>::max();
1470         bool isFixed = false;
1471         renderText->absoluteQuadsForRange(quads, startOffset, endOffset, useSelectionHeight, &isFixed);
1472         allFixed &= isFixed;
1473         someFixed |= isFixed;
1474     }
1475
1476     if (inFixed)
1477         *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition);
1478 }
1479
1480 #ifndef NDEBUG
1481 void Range::formatForDebugger(char* buffer, unsigned length) const
1482 {
1483     StringBuilder result;
1484
1485     const int FormatBufferSize = 1024;
1486     char s[FormatBufferSize];
1487     result.appendLiteral("from offset ");
1488     result.appendNumber(m_start.offset());
1489     result.appendLiteral(" of ");
1490     m_start.container()->formatForDebugger(s, FormatBufferSize);
1491     result.append(s);
1492     result.appendLiteral(" to offset ");
1493     result.appendNumber(m_end.offset());
1494     result.appendLiteral(" of ");
1495     m_end.container()->formatForDebugger(s, FormatBufferSize);
1496     result.append(s);
1497
1498     strncpy(buffer, result.toString().utf8().data(), length - 1);
1499 }
1500 #endif
1501
1502 bool areRangesEqual(const Range* a, const Range* b)
1503 {
1504     if (a == b)
1505         return true;
1506     if (!a || !b)
1507         return false;
1508     return a->startPosition() == b->startPosition() && a->endPosition() == b->endPosition();
1509 }
1510
1511 PassRefPtrWillBeRawPtr<Range> rangeOfContents(Node* node)
1512 {
1513     ASSERT(node);
1514     RefPtrWillBeRawPtr<Range> range = Range::create(node->document());
1515     range->selectNodeContents(node, IGNORE_EXCEPTION);
1516     return range.release();
1517 }
1518
1519 static inline void boundaryNodeChildrenChanged(RangeBoundaryPoint& boundary, ContainerNode* container)
1520 {
1521     if (!boundary.childBefore())
1522         return;
1523     if (boundary.container() != container)
1524         return;
1525     boundary.invalidateOffset();
1526 }
1527
1528 void Range::nodeChildrenChanged(ContainerNode* container)
1529 {
1530     ASSERT(container);
1531     ASSERT(container->document() == m_ownerDocument);
1532     boundaryNodeChildrenChanged(m_start, container);
1533     boundaryNodeChildrenChanged(m_end, container);
1534 }
1535
1536 static inline void boundaryNodeChildrenWillBeRemoved(RangeBoundaryPoint& boundary, ContainerNode& container)
1537 {
1538     for (Node* nodeToBeRemoved = container.firstChild(); nodeToBeRemoved; nodeToBeRemoved = nodeToBeRemoved->nextSibling()) {
1539         if (boundary.childBefore() == nodeToBeRemoved) {
1540             boundary.setToStartOfNode(container);
1541             return;
1542         }
1543
1544         for (Node* n = boundary.container(); n; n = n->parentNode()) {
1545             if (n == nodeToBeRemoved) {
1546                 boundary.setToStartOfNode(container);
1547                 return;
1548             }
1549         }
1550     }
1551 }
1552
1553 void Range::nodeChildrenWillBeRemoved(ContainerNode& container)
1554 {
1555     ASSERT(container.document() == m_ownerDocument);
1556     boundaryNodeChildrenWillBeRemoved(m_start, container);
1557     boundaryNodeChildrenWillBeRemoved(m_end, container);
1558 }
1559
1560 static inline void boundaryNodeWillBeRemoved(RangeBoundaryPoint& boundary, Node& nodeToBeRemoved)
1561 {
1562     if (boundary.childBefore() == nodeToBeRemoved) {
1563         boundary.childBeforeWillBeRemoved();
1564         return;
1565     }
1566
1567     for (Node* n = boundary.container(); n; n = n->parentNode()) {
1568         if (n == nodeToBeRemoved) {
1569             boundary.setToBeforeChild(nodeToBeRemoved);
1570             return;
1571         }
1572     }
1573 }
1574
1575 void Range::nodeWillBeRemoved(Node& node)
1576 {
1577     ASSERT(node.document() == m_ownerDocument);
1578     ASSERT(node != m_ownerDocument.get());
1579
1580     // FIXME: Once DOMNodeRemovedFromDocument mutation event removed, we
1581     // should change following if-statement to ASSERT(!node->parentNode).
1582     if (!node.parentNode())
1583         return;
1584     boundaryNodeWillBeRemoved(m_start, node);
1585     boundaryNodeWillBeRemoved(m_end, node);
1586 }
1587
1588 static inline void boundaryTextInserted(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
1589 {
1590     if (boundary.container() != text)
1591         return;
1592     unsigned boundaryOffset = boundary.offset();
1593     if (offset >= boundaryOffset)
1594         return;
1595     boundary.setOffset(boundaryOffset + length);
1596 }
1597
1598 void Range::didInsertText(Node* text, unsigned offset, unsigned length)
1599 {
1600     ASSERT(text);
1601     ASSERT(text->document() == m_ownerDocument);
1602     boundaryTextInserted(m_start, text, offset, length);
1603     boundaryTextInserted(m_end, text, offset, length);
1604 }
1605
1606 static inline void boundaryTextRemoved(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
1607 {
1608     if (boundary.container() != text)
1609         return;
1610     unsigned boundaryOffset = boundary.offset();
1611     if (offset >= boundaryOffset)
1612         return;
1613     if (offset + length >= boundaryOffset)
1614         boundary.setOffset(offset);
1615     else
1616         boundary.setOffset(boundaryOffset - length);
1617 }
1618
1619 void Range::didRemoveText(Node* text, unsigned offset, unsigned length)
1620 {
1621     ASSERT(text);
1622     ASSERT(text->document() == m_ownerDocument);
1623     boundaryTextRemoved(m_start, text, offset, length);
1624     boundaryTextRemoved(m_end, text, offset, length);
1625 }
1626
1627 static inline void boundaryTextNodesMerged(RangeBoundaryPoint& boundary, const NodeWithIndex& oldNode, unsigned offset)
1628 {
1629     if (boundary.container() == oldNode.node())
1630         boundary.set(oldNode.node().previousSibling(), boundary.offset() + offset, 0);
1631     else if (boundary.container() == oldNode.node().parentNode() && boundary.offset() == oldNode.index())
1632         boundary.set(oldNode.node().previousSibling(), offset, 0);
1633 }
1634
1635 void Range::didMergeTextNodes(const NodeWithIndex& oldNode, unsigned offset)
1636 {
1637     ASSERT(oldNode.node().document() == m_ownerDocument);
1638     ASSERT(oldNode.node().parentNode());
1639     ASSERT(oldNode.node().isTextNode());
1640     ASSERT(oldNode.node().previousSibling());
1641     ASSERT(oldNode.node().previousSibling()->isTextNode());
1642     boundaryTextNodesMerged(m_start, oldNode, offset);
1643     boundaryTextNodesMerged(m_end, oldNode, offset);
1644 }
1645
1646 void Range::updateOwnerDocumentIfNeeded()
1647 {
1648     ASSERT(m_start.container());
1649     ASSERT(m_end.container());
1650     Document& newDocument = m_start.container()->document();
1651     ASSERT(newDocument == m_end.container()->document());
1652     if (newDocument == m_ownerDocument)
1653         return;
1654     m_ownerDocument->detachRange(this);
1655     m_ownerDocument = &newDocument;
1656     m_ownerDocument->attachRange(this);
1657 }
1658
1659 static inline void boundaryTextNodeSplit(RangeBoundaryPoint& boundary, Text& oldNode)
1660 {
1661     Node* boundaryContainer = boundary.container();
1662     unsigned boundaryOffset = boundary.offset();
1663     if (boundary.childBefore() == &oldNode)
1664         boundary.set(boundaryContainer, boundaryOffset + 1, oldNode.nextSibling());
1665     else if (boundary.container() == &oldNode && boundaryOffset > oldNode.length())
1666         boundary.set(oldNode.nextSibling(), boundaryOffset - oldNode.length(), 0);
1667 }
1668
1669 void Range::didSplitTextNode(Text& oldNode)
1670 {
1671     ASSERT(oldNode.document() == m_ownerDocument);
1672     ASSERT(oldNode.parentNode());
1673     ASSERT(oldNode.nextSibling());
1674     ASSERT(oldNode.nextSibling()->isTextNode());
1675     boundaryTextNodeSplit(m_start, oldNode);
1676     boundaryTextNodeSplit(m_end, oldNode);
1677     ASSERT(boundaryPointsValid());
1678 }
1679
1680 void Range::expand(const String& unit, ExceptionState& exceptionState)
1681 {
1682     VisiblePosition start(startPosition());
1683     VisiblePosition end(endPosition());
1684     if (unit == "word") {
1685         start = startOfWord(start);
1686         end = endOfWord(end);
1687     } else if (unit == "sentence") {
1688         start = startOfSentence(start);
1689         end = endOfSentence(end);
1690     } else if (unit == "block") {
1691         start = startOfParagraph(start);
1692         end = endOfParagraph(end);
1693     } else if (unit == "document") {
1694         start = startOfDocument(start);
1695         end = endOfDocument(end);
1696     } else
1697         return;
1698     setStart(start.deepEquivalent().containerNode(), start.deepEquivalent().computeOffsetInContainerNode(), exceptionState);
1699     setEnd(end.deepEquivalent().containerNode(), end.deepEquivalent().computeOffsetInContainerNode(), exceptionState);
1700 }
1701
1702 PassRefPtrWillBeRawPtr<ClientRectList> Range::getClientRects() const
1703 {
1704     m_ownerDocument->updateLayoutIgnorePendingStylesheets();
1705
1706     Vector<FloatQuad> quads;
1707     getBorderAndTextQuads(quads);
1708
1709     return ClientRectList::create(quads);
1710 }
1711
1712 PassRefPtrWillBeRawPtr<ClientRect> Range::getBoundingClientRect() const
1713 {
1714     return ClientRect::create(boundingRect());
1715 }
1716
1717 void Range::getBorderAndTextQuads(Vector<FloatQuad>& quads) const
1718 {
1719     Node* startContainer = m_start.container();
1720     Node* endContainer = m_end.container();
1721     Node* stopNode = pastLastNode();
1722
1723     WillBeHeapHashSet<RawPtrWillBeMember<Node>> nodeSet;
1724     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(*node)) {
1725         if (node->isElementNode())
1726             nodeSet.add(node);
1727     }
1728
1729     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(*node)) {
1730         if (node->isElementNode()) {
1731             if (!nodeSet.contains(node->parentNode())) {
1732                 if (RenderBoxModelObject* renderBoxModelObject = toElement(node)->renderBoxModelObject()) {
1733                     Vector<FloatQuad> elementQuads;
1734                     renderBoxModelObject->absoluteQuads(elementQuads);
1735                     m_ownerDocument->adjustFloatQuadsForScrollAndAbsoluteZoom(elementQuads, *renderBoxModelObject);
1736
1737                     quads.appendVector(elementQuads);
1738                 }
1739             }
1740         } else if (node->isTextNode()) {
1741             if (RenderText* renderText = toText(node)->renderer()) {
1742                 int startOffset = (node == startContainer) ? m_start.offset() : 0;
1743                 int endOffset = (node == endContainer) ? m_end.offset() : INT_MAX;
1744
1745                 Vector<FloatQuad> textQuads;
1746                 renderText->absoluteQuadsForRange(textQuads, startOffset, endOffset);
1747                 m_ownerDocument->adjustFloatQuadsForScrollAndAbsoluteZoom(textQuads, *renderText);
1748
1749                 quads.appendVector(textQuads);
1750             }
1751         }
1752     }
1753 }
1754
1755 FloatRect Range::boundingRect() const
1756 {
1757     m_ownerDocument->updateLayoutIgnorePendingStylesheets();
1758
1759     Vector<FloatQuad> quads;
1760     getBorderAndTextQuads(quads);
1761
1762     FloatRect result;
1763     for (const FloatQuad& quad : quads)
1764         result.unite(quad.boundingBox());
1765
1766     return result;
1767 }
1768
1769 void Range::trace(Visitor* visitor)
1770 {
1771     visitor->trace(m_ownerDocument);
1772     visitor->trace(m_start);
1773     visitor->trace(m_end);
1774 }
1775
1776 } // namespace blink
1777
1778 #ifndef NDEBUG
1779
1780 void showTree(const blink::Range* range)
1781 {
1782     if (range && range->boundaryPointsValid()) {
1783         range->startContainer()->showTreeAndMark(range->startContainer(), "S", range->endContainer(), "E");
1784         fprintf(stderr, "start offset: %d, end offset: %d\n", range->startOffset(), range->endOffset());
1785     }
1786 }
1787
1788 #endif