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     processContents(Delete, ec);
 493 }
 494
 495 bool Range::intersectsNode(Node* refNode, ExceptionCode& ec) const
 496 {
 497     if (!refNode) {
 498         ec = TypeError;
 499         return false;
 500     }
 501
 502     if (!refNode->inDocument() || &refNode->document() != &ownerDocument())
 503         return false;
 504
 505     ContainerNode* parentNode = refNode->parentNode();
 506     if (!parentNode)
 507         return true;
 508
 509     unsigned nodeIndex = refNode->computeNodeIndex();
 510
 511     // If (parent, offset) is before end and (parent, offset + 1) is after start, return true.
 512     // Otherwise, return false.
 513     short compareFirst = comparePoint(parentNode, nodeIndex, ec);
 514     short compareSecond = comparePoint(parentNode, nodeIndex + 1, ec);
 515
 516     bool isFirstBeforeEnd = m_start == m_end ? compareFirst < 0 : compareFirst <= 0;
 517     bool isSecondAfterStart = m_start == m_end ? compareSecond > 0 : compareSecond >= 0;
 518
 519     return isFirstBeforeEnd && isSecondAfterStart;
 520 }
 521
 522 static inline Node* highestAncestorUnderCommonRoot(Node* node, Node* commonRoot)
 523 {
 524     if (node == commonRoot)
 525         return 0;
 526
 527     ASSERT(commonRoot->contains(node));
 528
 529     while (node->parentNode() != commonRoot)
 530         node = node->parentNode();
 531
 532     return node;
 533 }
 534
 535 static inline Node* childOfCommonRootBeforeOffset(Node* container, unsigned offset, Node* commonRoot)
 536 {
 537     ASSERT(container);
 538     ASSERT(commonRoot);
 539
 540     if (!commonRoot->contains(container))
 541         return 0;
 542
 543     if (container == commonRoot) {
 544         container = container->firstChild();
 545         for (unsigned i = 0; container && i < offset; i++)
 546             container = container->nextSibling();
 547     } else {
 548         while (container->parentNode() != commonRoot)
 549             container = container->parentNode();
 550     }
 551
 552     return container;
 553 }
 554
 555 static inline unsigned lengthOfContentsInNode(Node& node)
 556 {
 557     // This switch statement must be consistent with that of Range::processContentsBetweenOffsets.
 558     switch (node.nodeType()) {
 559     case Node::DOCUMENT_TYPE_NODE:
 560         return 0;
 561     case Node::TEXT_NODE:
 562     case Node::CDATA_SECTION_NODE:
 563     case Node::COMMENT_NODE:
 564     case Node::PROCESSING_INSTRUCTION_NODE:
 565         return downcast<CharacterData>(node).length();
 566     case Node::ELEMENT_NODE:
 567     case Node::ATTRIBUTE_NODE:
 568     case Node::DOCUMENT_NODE:
 569     case Node::DOCUMENT_FRAGMENT_NODE:
 570         return downcast<ContainerNode>(node).countChildNodes();
 571     }
 572     ASSERT_NOT_REACHED();
 573     return 0;
 574 }
 575
 576 RefPtr<DocumentFragment> Range::processContents(ActionType action, ExceptionCode& ec)
 577 {
 578     typedef Vector<RefPtr<Node>> NodeVector;
 579
 580     RefPtr<DocumentFragment> fragment;
 581     if (action == Extract || action == Clone)
 582         fragment = DocumentFragment::create(ownerDocument());
 583
 584     if (collapsed())
 585         return fragment;
 586
 587     RefPtr<Node> commonRoot = commonAncestorContainer();
 588     ASSERT(commonRoot);
 589
 590     if (&startContainer() == &endContainer()) {
 591         processContentsBetweenOffsets(action, fragment, &startContainer(), m_start.offset(), m_end.offset(), ec);
 592         return fragment;
 593     }
 594
 595     // Since mutation events can modify the range during the process, the boundary points need to be saved.
 596     RangeBoundaryPoint originalStart(m_start);
 597     RangeBoundaryPoint originalEnd(m_end);
 598
 599     // what is the highest node that partially selects the start / end of the range?
 600     RefPtr<Node> partialStart = highestAncestorUnderCommonRoot(originalStart.container(), commonRoot.get());
 601     RefPtr<Node> partialEnd = highestAncestorUnderCommonRoot(originalEnd.container(), commonRoot.get());
 602
 603     // Start and end containers are different.
 604     // There are three possibilities here:
 605     // 1. Start container == commonRoot (End container must be a descendant)
 606     // 2. End container == commonRoot (Start container must be a descendant)
 607     // 3. Neither is commonRoot, they are both descendants
 608     //
 609     // In case 3, we grab everything after the start (up until a direct child
 610     // of commonRoot) into leftContents, and everything before the end (up until
 611     // a direct child of commonRoot) into rightContents. Then we process all
 612     // commonRoot children between leftContents and rightContents
 613     //
 614     // In case 1 or 2, we skip either processing of leftContents or rightContents,
 615     // in which case the last lot of nodes either goes from the first or last
 616     // child of commonRoot.
 617     //
 618     // These are deleted, cloned, or extracted (i.e. both) depending on action.
 619
 620     // Note that we are verifying that our common root hierarchy is still intact
 621     // after any DOM mutation event, at various stages below. See webkit bug 60350.
 622
 623     RefPtr<Node> leftContents;
 624     if (originalStart.container() != commonRoot && commonRoot->contains(originalStart.container())) {
 625         leftContents = processContentsBetweenOffsets(action, 0, originalStart.container(), originalStart.offset(), lengthOfContentsInNode(*originalStart.container()), ec);
 626         leftContents = processAncestorsAndTheirSiblings(action, originalStart.container(), ProcessContentsForward, leftContents, commonRoot.get(), ec);
 627     }
 628
 629     RefPtr<Node> rightContents;
 630     if (&endContainer() != commonRoot && commonRoot->contains(originalEnd.container())) {
 631         rightContents = processContentsBetweenOffsets(action, 0, originalEnd.container(), 0, originalEnd.offset(), ec);
 632         rightContents = processAncestorsAndTheirSiblings(action, originalEnd.container(), ProcessContentsBackward, rightContents, commonRoot.get(), ec);
 633     }
 634
 635     // delete all children of commonRoot between the start and end container
 636     RefPtr<Node> processStart = childOfCommonRootBeforeOffset(originalStart.container(), originalStart.offset(), commonRoot.get());
 637     if (processStart && originalStart.container() != commonRoot) // processStart contains nodes before m_start.
 638         processStart = processStart->nextSibling();
 639     RefPtr<Node> processEnd = childOfCommonRootBeforeOffset(originalEnd.container(), originalEnd.offset(), commonRoot.get());
 640
 641     // Collapse the range, making sure that the result is not within a node that was partially selected.
 642     ec = 0;
 643     if (action == Extract || action == Delete) {
 644         if (partialStart && commonRoot->contains(partialStart.get()))
 645             setStart(partialStart->parentNode(), partialStart->computeNodeIndex() + 1, ec);
 646         else if (partialEnd && commonRoot->contains(partialEnd.get()))
 647             setStart(partialEnd->parentNode(), partialEnd->computeNodeIndex(), ec);
 648         if (ec)
 649             return nullptr;
 650         m_end = m_start;
 651     }
 652
 653     // Now add leftContents, stuff in between, and rightContents to the fragment
 654     // (or just delete the stuff in between)
 655
 656     if ((action == Extract || action == Clone) && leftContents)
 657         fragment->appendChild(*leftContents, ec);
 658
 659     if (processStart) {
 660         NodeVector nodes;
 661         for (Node* n = processStart.get(); n && n != processEnd; n = n->nextSibling())
 662             nodes.append(n);
 663         processNodes(action, nodes, commonRoot, fragment, ec);
 664     }
 665
 666     if ((action == Extract || action == Clone) && rightContents)
 667         fragment->appendChild(*rightContents, ec);
 668
 669     return fragment;
 670 }
 671
 672 static inline void deleteCharacterData(PassRefPtr<CharacterData> data, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
 673 {
 674     if (data->length() - endOffset)
 675         data->deleteData(endOffset, data->length() - endOffset, ec);
 676     if (startOffset)
 677         data->deleteData(0, startOffset, ec);
 678 }
 679
 680 RefPtr<Node> Range::processContentsBetweenOffsets(ActionType action, PassRefPtr<DocumentFragment> fragment, Node* container, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
 681 {
 682     ASSERT(container);
 683     ASSERT(startOffset <= endOffset);
 684
 685     // This switch statement must be consistent with that of lengthOfContentsInNode.
 686     RefPtr<Node> result;
 687     switch (container->nodeType()) {
 688     case Node::TEXT_NODE:
 689     case Node::CDATA_SECTION_NODE:
 690     case Node::COMMENT_NODE:
 691         endOffset = std::min(endOffset, static_cast<CharacterData*>(container)->length());
 692         startOffset = std::min(startOffset, endOffset);
 693         if (action == Extract || action == Clone) {
 694             RefPtr<CharacterData> c = static_cast<CharacterData*>(container->cloneNode(true).ptr());
 695             deleteCharacterData(c, startOffset, endOffset, ec);
 696             if (fragment) {
 697                 result = fragment;
 698                 result->appendChild(c.release(), ec);
 699             } else
 700                 result = c.release();
 701         }
 702         if (action == Extract || action == Delete)
 703             downcast<CharacterData>(*container).deleteData(startOffset, endOffset - startOffset, ec);
 704         break;
 705     case Node::PROCESSING_INSTRUCTION_NODE:
 706         endOffset = std::min(endOffset, static_cast<ProcessingInstruction*>(container)->data().length());
 707         startOffset = std::min(startOffset, endOffset);
 708         if (action == Extract || action == Clone) {
 709             RefPtr<ProcessingInstruction> c = static_cast<ProcessingInstruction*>(container->cloneNode(true).ptr());
 710             c->setData(c->data().substring(startOffset, endOffset - startOffset));
 711             if (fragment) {
 712                 result = fragment;
 713                 result->appendChild(c.release(), ec);
 714             } else
 715                 result = c.release();
 716         }
 717         if (action == Extract || action == Delete) {
 718             ProcessingInstruction& pi = downcast<ProcessingInstruction>(*container);
 719             String data(pi.data());
 720             data.remove(startOffset, endOffset - startOffset);
 721             pi.setData(data);
 722         }
 723         break;
 724     case Node::ELEMENT_NODE:
 725     case Node::ATTRIBUTE_NODE:
 726     case Node::DOCUMENT_NODE:
 727     case Node::DOCUMENT_TYPE_NODE:
 728     case Node::DOCUMENT_FRAGMENT_NODE:
 729         // FIXME: Should we assert that some nodes never appear here?
 730         if (action == Extract || action == Clone) {
 731             if (fragment)
 732                 result = fragment;
 733             else
 734                 result = container->cloneNode(false);
 735         }
 736
 737         Node* n = container->firstChild();
 738         Vector<RefPtr<Node>> nodes;
 739         for (unsigned i = startOffset; n && i; i--)
 740             n = n->nextSibling();
 741         for (unsigned i = startOffset; n && i < endOffset; i++, n = n->nextSibling()) {
 742             if (action != Delete && n->isDocumentTypeNode()) {
 743                 ec = HIERARCHY_REQUEST_ERR;
 744                 return nullptr;
 745             }
 746             nodes.append(n);
 747         }
 748
 749         processNodes(action, nodes, container, result, ec);
 750         break;
 751     }
 752
 753     return result;
 754 }
 755
 756 void Range::processNodes(ActionType action, Vector<RefPtr<Node>>& nodes, PassRefPtr<Node> oldContainer, PassRefPtr<Node> newContainer, ExceptionCode& ec)
 757 {
 758     for (auto& node : nodes) {
 759         switch (action) {
 760         case Delete:
 761             oldContainer->removeChild(node.get(), ec);
 762             break;
 763         case Extract:
 764             newContainer->appendChild(node.release(), ec); // will remove n from its parent
 765             break;
 766         case Clone:
 767             newContainer->appendChild(node->cloneNode(true), ec);
 768             break;
 769         }
 770     }
 771 }
 772
 773 RefPtr<Node> Range::processAncestorsAndTheirSiblings(ActionType action, Node* container, ContentsProcessDirection direction, PassRefPtr<Node> passedClonedContainer, Node* commonRoot, ExceptionCode& ec)
 774 {
 775     typedef Vector<RefPtr<Node>> NodeVector;
 776
 777     RefPtr<Node> clonedContainer = passedClonedContainer;
 778     Vector<RefPtr<Node>> ancestors;
 779     for (ContainerNode* n = container->parentNode(); n && n != commonRoot; n = n->parentNode())
 780         ancestors.append(n);
 781
 782     RefPtr<Node> firstChildInAncestorToProcess = direction == ProcessContentsForward ? container->nextSibling() : container->previousSibling();
 783     for (auto& ancestor : ancestors) {
 784         if (action == Extract || action == Clone) {
 785             if (RefPtr<Node> clonedAncestor = ancestor->cloneNode(false)) { // Might have been removed already during mutation event.
 786                 clonedAncestor->appendChild(clonedContainer, ec);
 787                 clonedContainer = clonedAncestor;
 788             }
 789         }
 790
 791         // Copy siblings of an ancestor of start/end containers
 792         // FIXME: This assertion may fail if DOM is modified during mutation event
 793         // FIXME: Share code with Range::processNodes
 794         ASSERT(!firstChildInAncestorToProcess || firstChildInAncestorToProcess->parentNode() == ancestor);
 795
 796         NodeVector nodes;
 797         for (Node* child = firstChildInAncestorToProcess.get(); child;
 798             child = (direction == ProcessContentsForward) ? child->nextSibling() : child->previousSibling())
 799             nodes.append(child);
 800
 801         for (auto& child : nodes) {
 802             switch (action) {
 803             case Delete:
 804                 ancestor->removeChild(child.get(), ec);
 805                 break;
 806             case Extract: // will remove child from ancestor
 807                 if (direction == ProcessContentsForward)
 808                     clonedContainer->appendChild(child.get(), ec);
 809                 else
 810                     clonedContainer->insertBefore(child.get(), clonedContainer->firstChild(), ec);
 811                 break;
 812             case Clone:
 813                 if (direction == ProcessContentsForward)
 814                     clonedContainer->appendChild(child->cloneNode(true), ec);
 815                 else
 816                     clonedContainer->insertBefore(child->cloneNode(true), clonedContainer->firstChild(), ec);
 817                 break;
 818             }
 819         }
 820         firstChildInAncestorToProcess = direction == ProcessContentsForward ? ancestor->nextSibling() : ancestor->previousSibling();
 821     }
 822
 823     return clonedContainer;
 824 }
 825
 826 RefPtr<DocumentFragment> Range::extractContents(ExceptionCode& ec)
 827 {
 828     return processContents(Extract, ec);
 829 }
 830
 831 RefPtr<DocumentFragment> Range::cloneContents(ExceptionCode& ec)
 832 {
 833     return processContents(Clone, ec);
 834 }
 835
 836 void Range::insertNode(RefPtr<Node>&& node, ExceptionCode& ec)
 837 {
 838     if (!node) {
 839         ec = TypeError;
 840         return;
 841     }
 842
 843     bool startIsCharacterData = is<CharacterData>(startContainer());
 844     if (startIsCharacterData && !startContainer().parentNode()) {
 845         ec = HIERARCHY_REQUEST_ERR;
 846         return;
 847     }
 848     bool startIsText = startIsCharacterData && startContainer().nodeType() == Node::TEXT_NODE;
 849     RefPtr<Node> referenceNode = startIsText ? &startContainer() : startContainer().traverseToChildAt(startOffset());
 850     Node* parentNode = referenceNode ? referenceNode->parentNode() : &startContainer();
 851     if (!is<ContainerNode>(parentNode)) {
 852         ec = HIERARCHY_REQUEST_ERR;
 853         return;
 854     }
 855
 856     Ref<ContainerNode> parent = downcast<ContainerNode>(*parentNode);
 857
 858     ec = 0;
 859     if (!parent->ensurePreInsertionValidity(*node, referenceNode.get(), ec))
 860         return;
 861
 862     EventQueueScope scope;
 863     if (startIsText) {
 864         referenceNode = downcast<Text>(startContainer()).splitText(startOffset(), ec);
 865         if (ec)
 866             return;
 867     }
 868
 869     if (referenceNode == node)
 870         referenceNode = referenceNode->nextSibling();
 871
 872     node->remove(ec);
 873     if (ec)
 874         return;
 875
 876     unsigned newOffset = referenceNode ? referenceNode->computeNodeIndex() : parent->countChildNodes();
 877     if (is<DocumentFragment>(*node))
 878         newOffset += downcast<DocumentFragment>(*node).countChildNodes();
 879     else
 880         ++newOffset;
 881
 882     parent->insertBefore(node.releaseNonNull(), referenceNode.get(), ec);
 883     if (ec)
 884         return;
 885
 886     if (collapsed())
 887         setEnd(parent.ptr(), newOffset, ec);
 888 }
 889
 890 String Range::toString() const
 891 {
 892     StringBuilder builder;
 893
 894     Node* pastLast = pastLastNode();
 895     for (Node* n = firstNode(); n != pastLast; n = NodeTraversal::next(*n)) {
 896         if (n->nodeType() == Node::TEXT_NODE || n->nodeType() == Node::CDATA_SECTION_NODE) {
 897             const String& data = static_cast<CharacterData*>(n)->data();
 898             int length = data.length();
 899             int start = n == &startContainer() ? std::min(std::max(0, m_start.offset()), length) : 0;
 900             int end = n == &endContainer() ? std::min(std::max(start, m_end.offset()), length) : length;
 901             builder.append(data, start, end - start);
 902         }
 903     }
 904
 905     return builder.toString();
 906 }
 907
 908 String Range::toHTML() const
 909 {
 910     return createMarkup(*this);
 911 }
 912
 913 String Range::text() const
 914 {
 915     // We need to update layout, since plainText uses line boxes in the render tree.
 916     // FIXME: As with innerText, we'd like this to work even if there are no render objects.
 917     startContainer().document().updateLayout();
 918
 919     return plainText(this);
 920 }
 921
 922 RefPtr<DocumentFragment> Range::createContextualFragment(const String& markup, ExceptionCode& ec)
 923 {
 924     Node* element = startContainer().isElementNode() ? &startContainer() : startContainer().parentNode();
 925     if (!element || !element->isHTMLElement()) {
 926         ec = NOT_SUPPORTED_ERR;
 927         return nullptr;
 928     }
 929
 930     return WebCore::createContextualFragment(markup, downcast<HTMLElement>(element), AllowScriptingContentAndDoNotMarkAlreadyStarted, ec);
 931 }
 932
 933
 934 void Range::detach()
 935 {
 936     // This is now a no-op as per the DOM specification.
 937 }
 938
 939 Node* Range::checkNodeWOffset(Node* n, int offset, ExceptionCode& ec) const
 940 {
 941     switch (n->nodeType()) {
 942         case Node::DOCUMENT_TYPE_NODE:
 943             ec = INVALID_NODE_TYPE_ERR;
 944             return nullptr;
 945         case Node::CDATA_SECTION_NODE:
 946         case Node::COMMENT_NODE:
 947         case Node::TEXT_NODE:
 948         case Node::PROCESSING_INSTRUCTION_NODE:
 949             if (static_cast<unsigned>(offset) > downcast<CharacterData>(*n).length())
 950                 ec = INDEX_SIZE_ERR;
 951             return nullptr;
 952         case Node::ATTRIBUTE_NODE:
 953         case Node::DOCUMENT_FRAGMENT_NODE:
 954         case Node::DOCUMENT_NODE:
 955         case Node::ELEMENT_NODE: {
 956             if (!offset)
 957                 return nullptr;
 958             Node* childBefore = n->traverseToChildAt(offset - 1);
 959             if (!childBefore)
 960                 ec = INDEX_SIZE_ERR;
 961             return childBefore;
 962         }
 963     }
 964     ASSERT_NOT_REACHED();
 965     return nullptr;
 966 }
 967
 968 Ref<Range> Range::cloneRange() const
 969 {
 970     return Range::create(ownerDocument(), &startContainer(), m_start.offset(), &endContainer(), m_end.offset());
 971 }
 972
 973 void Range::setStartAfter(Node* refNode, ExceptionCode& ec)
 974 {
 975     if (!refNode) {
 976         ec = TypeError;
 977         return;
 978     }
 979
 980     if (!refNode->parentNode()) {
 981         ec = INVALID_NODE_TYPE_ERR;
 982         return;
 983     }
 984
 985     setStart(refNode->parentNode(), refNode->computeNodeIndex() + 1, ec);
 986 }
 987
 988 void Range::setEndBefore(Node* refNode, ExceptionCode& ec)
 989 {
 990     if (!refNode) {
 991         ec = TypeError;
 992         return;
 993     }
 994
 995     if (!refNode->parentNode()) {
 996         ec = INVALID_NODE_TYPE_ERR;
 997         return;
 998     }
 999
1000     setEnd(refNode->parentNode(), refNode->computeNodeIndex(), ec);
1001 }
1002
1003 void Range::setEndAfter(Node* refNode, ExceptionCode& ec)
1004 {
1005     if (!refNode) {
1006         ec = TypeError;
1007         return;
1008     }
1009
1010     if (!refNode->parentNode()) {
1011         ec = INVALID_NODE_TYPE_ERR;
1012         return;
1013     }
1014
1015     setEnd(refNode->parentNode(), refNode->computeNodeIndex() + 1, ec);
1016 }
1017
1018 void Range::selectNode(Node* refNode, ExceptionCode& ec)
1019 {
1020     if (!refNode) {
1021         ec = TypeError;
1022         return;
1023     }
1024
1025     if (!refNode->parentNode()) {
1026         ec = INVALID_NODE_TYPE_ERR;
1027         return;
1028     }
1029
1030     if (&ownerDocument() != &refNode->document())
1031         setDocument(refNode->document());
1032
1033     unsigned index = refNode->computeNodeIndex();
1034     ec = 0;
1035     setStart(refNode->parentNode(), index, ec);
1036     if (ec)
1037         return;
1038     setEnd(refNode->parentNode(), index + 1, ec);
1039 }
1040
1041 void Range::selectNodeContents(Node* refNode, ExceptionCode& ec)
1042 {
1043     if (!refNode) {
1044         ec = TypeError;
1045         return;
1046     }
1047
1048     if (refNode->isDocumentTypeNode()) {
1049         ec = INVALID_NODE_TYPE_ERR;
1050         return;
1051     }
1052
1053     if (&ownerDocument() != &refNode->document())
1054         setDocument(refNode->document());
1055
1056     m_start.setToStartOfNode(refNode);
1057     m_end.setToEndOfNode(refNode);
1058 }
1059
1060 void Range::surroundContents(PassRefPtr<Node> passNewParent, ExceptionCode& ec)
1061 {
1062     RefPtr<Node> newParent = passNewParent;
1063
1064     if (!newParent) {
1065         ec = TypeError;
1066         return;
1067     }
1068
1069     // INVALID_STATE_ERR: Raised if the Range partially selects a non-Text node.
1070     // https://dom.spec.whatwg.org/#dom-range-surroundcontents (step 1).
1071     Node* startNonTextContainer = &startContainer();
1072     if (startNonTextContainer->nodeType() == Node::TEXT_NODE)
1073         startNonTextContainer = startNonTextContainer->parentNode();
1074     Node* endNonTextContainer = &endContainer();
1075     if (endNonTextContainer->nodeType() == Node::TEXT_NODE)
1076         endNonTextContainer = endNonTextContainer->parentNode();
1077     if (startNonTextContainer != endNonTextContainer) {
1078         ec = INVALID_STATE_ERR;
1079         return;
1080     }
1081
1082     // INVALID_NODE_TYPE_ERR: Raised if node is an Attr, Entity, DocumentType,
1083     // Document, or DocumentFragment node.
1084     switch (newParent->nodeType()) {
1085         case Node::ATTRIBUTE_NODE:
1086         case Node::DOCUMENT_FRAGMENT_NODE:
1087         case Node::DOCUMENT_NODE:
1088         case Node::DOCUMENT_TYPE_NODE:
1089             ec = INVALID_NODE_TYPE_ERR;
1090             return;
1091         case Node::CDATA_SECTION_NODE:
1092         case Node::COMMENT_NODE:
1093         case Node::ELEMENT_NODE:
1094         case Node::PROCESSING_INSTRUCTION_NODE:
1095         case Node::TEXT_NODE:
1096             break;
1097     }
1098
1099     // Raise a HIERARCHY_REQUEST_ERR if startContainer() doesn't accept children like newParent.
1100     Node* parentOfNewParent = &startContainer();
1101
1102     // If startContainer() is a character data node, it will be split and it will be its parent that will
1103     // need to accept newParent (or in the case of a comment, it logically "would" be inserted into the parent,
1104     // although this will fail below for another reason).
1105     if (parentOfNewParent->isCharacterDataNode())
1106         parentOfNewParent = parentOfNewParent->parentNode();
1107     if (!parentOfNewParent || !parentOfNewParent->childTypeAllowed(newParent->nodeType())) {
1108         ec = HIERARCHY_REQUEST_ERR;
1109         return;
1110     }
1111
1112     if (newParent->contains(&startContainer())) {
1113         ec = HIERARCHY_REQUEST_ERR;
1114         return;
1115     }
1116
1117     // FIXME: Do we need a check if the node would end up with a child node of a type not
1118     // allowed by the type of node?
1119
1120     ec = 0;
1121     while (Node* n = newParent->firstChild()) {
1122         downcast<ContainerNode>(*newParent).removeChild(*n, ec);
1123         if (ec)
1124             return;
1125     }
1126     RefPtr<DocumentFragment> fragment = extractContents(ec);
1127     if (ec)
1128         return;
1129     insertNode(newParent.copyRef(), ec);
1130     if (ec)
1131         return;
1132     newParent->appendChild(fragment.release(), ec);
1133     if (ec)
1134         return;
1135     selectNode(newParent.get(), ec);
1136 }
1137
1138 void Range::setStartBefore(Node* refNode, ExceptionCode& ec)
1139 {
1140     if (!refNode) {
1141         ec = TypeError;
1142         return;
1143     }
1144
1145     if (!refNode->parentNode()) {
1146         ec = INVALID_NODE_TYPE_ERR;
1147         return;
1148     }
1149
1150     setStart(refNode->parentNode(), refNode->computeNodeIndex(), ec);
1151 }
1152
1153 Node* Range::firstNode() const
1154 {
1155     if (startContainer().offsetInCharacters())
1156         return &startContainer();
1157     if (Node* child = startContainer().traverseToChildAt(m_start.offset()))
1158         return child;
1159     if (!m_start.offset())
1160         return &startContainer();
1161     return NodeTraversal::nextSkippingChildren(startContainer());
1162 }
1163
1164 ShadowRoot* Range::shadowRoot() const
1165 {
1166     return startContainer().containingShadowRoot();
1167 }
1168
1169 Node* Range::pastLastNode() const
1170 {
1171     if (endContainer().offsetInCharacters())
1172         return NodeTraversal::nextSkippingChildren(endContainer());
1173     if (Node* child = endContainer().traverseToChildAt(m_end.offset()))
1174         return child;
1175     return NodeTraversal::nextSkippingChildren(endContainer());
1176 }
1177
1178 IntRect Range::absoluteBoundingBox() const
1179 {
1180     IntRect result;
1181     Vector<IntRect> rects;
1182     absoluteTextRects(rects);
1183     for (auto& rect : rects)
1184         result.unite(rect);
1185     return result;
1186 }
1187
1188 void Range::absoluteTextRects(Vector<IntRect>& rects, bool useSelectionHeight, RangeInFixedPosition* inFixed) const
1189 {
1190     bool allFixed = true;
1191     bool someFixed = false;
1192
1193     Node* stopNode = pastLastNode();
1194     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(*node)) {
1195         RenderObject* renderer = node->renderer();
1196         if (!renderer)
1197             continue;
1198         bool isFixed = false;
1199         if (renderer->isBR())
1200             renderer->absoluteRects(rects, flooredLayoutPoint(renderer->localToAbsolute()));
1201         else if (is<RenderText>(*renderer)) {
1202             int startOffset = node == &startContainer() ? m_start.offset() : 0;
1203             int endOffset = node == &endContainer() ? m_end.offset() : std::numeric_limits<int>::max();
1204             rects.appendVector(downcast<RenderText>(*renderer).absoluteRectsForRange(startOffset, endOffset, useSelectionHeight, &isFixed));
1205         } else
1206             continue;
1207         allFixed &= isFixed;
1208         someFixed |= isFixed;
1209     }
1210
1211     if (inFixed)
1212         *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition);
1213 }
1214
1215 void Range::absoluteTextQuads(Vector<FloatQuad>& quads, bool useSelectionHeight, RangeInFixedPosition* inFixed) const
1216 {
1217     bool allFixed = true;
1218     bool someFixed = false;
1219
1220     Node* stopNode = pastLastNode();
1221     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(*node)) {
1222         RenderObject* renderer = node->renderer();
1223         if (!renderer)
1224             continue;
1225         bool isFixed = false;
1226         if (renderer->isBR())
1227             renderer->absoluteQuads(quads, &isFixed);
1228         else if (is<RenderText>(*renderer)) {
1229             int startOffset = node == &startContainer() ? m_start.offset() : 0;
1230             int endOffset = node == &endContainer() ? m_end.offset() : std::numeric_limits<int>::max();
1231             quads.appendVector(downcast<RenderText>(*renderer).absoluteQuadsForRange(startOffset, endOffset, useSelectionHeight, &isFixed));
1232         } else
1233             continue;
1234         allFixed &= isFixed;
1235         someFixed |= isFixed;
1236     }
1237
1238     if (inFixed)
1239         *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition);
1240 }
1241
1242 #if PLATFORM(IOS)
1243 static bool intervalsSufficientlyOverlap(int startA, int endA, int startB, int endB)
1244 {
1245     if (endA <= startA || endB <= startB)
1246         return false;
1247
1248     const float sufficientOverlap = .75;
1249
1250     int lengthA = endA - startA;
1251     int lengthB = endB - startB;
1252
1253     int maxStart = std::max(startA, startB);
1254     int minEnd = std::min(endA, endB);
1255
1256     if (maxStart > minEnd)
1257         return false;
1258
1259     return minEnd - maxStart >= sufficientOverlap * std::min(lengthA, lengthB);
1260 }
1261
1262 static inline void adjustLineHeightOfSelectionRects(Vector<SelectionRect>& rects, size_t numberOfRects, int lineNumber, int lineTop, int lineHeight)
1263 {
1264     ASSERT(rects.size() >= numberOfRects);
1265     for (size_t i = numberOfRects; i; ) {
1266         --i;
1267         if (rects[i].lineNumber())
1268             break;
1269         rects[i].setLineNumber(lineNumber);
1270         rects[i].setLogicalTop(lineTop);
1271         rects[i].setLogicalHeight(lineHeight);
1272     }
1273 }
1274
1275 static SelectionRect coalesceSelectionRects(const SelectionRect& original, const SelectionRect& previous)
1276 {
1277     SelectionRect result(unionRect(previous.rect(), original.rect()), original.isHorizontal(), original.pageNumber());
1278     result.setDirection(original.containsStart() || original.containsEnd() ? original.direction() : previous.direction());
1279     result.setContainsStart(previous.containsStart() || original.containsStart());
1280     result.setContainsEnd(previous.containsEnd() || original.containsEnd());
1281     result.setIsFirstOnLine(previous.isFirstOnLine() || original.isFirstOnLine());
1282     result.setIsLastOnLine(previous.isLastOnLine() || original.isLastOnLine());
1283     return result;
1284 }
1285
1286 // This function is similar in spirit to addLineBoxRects, but annotates the returned rectangles
1287 // with additional state which helps iOS draw selections in its unique way.
1288 void Range::collectSelectionRects(Vector<SelectionRect>& rects)
1289 {
1290     auto& startContainer = this->startContainer();
1291     auto& endContainer = this->endContainer();
1292     int startOffset = m_start.offset();
1293     int endOffset = m_end.offset();
1294
1295     Vector<SelectionRect> newRects;
1296     Node* stopNode = pastLastNode();
1297     bool hasFlippedWritingMode = startContainer.renderer() && startContainer.renderer()->style().isFlippedBlocksWritingMode();
1298     bool containsDifferentWritingModes = false;
1299     for (Node* node = firstNode(); node && node != stopNode; node = NodeTraversal::next(*node)) {
1300         RenderObject* renderer = node->renderer();
1301         // Only ask leaf render objects for their line box rects.
1302         if (renderer && !renderer->firstChildSlow() && renderer->style().userSelect() != SELECT_NONE) {
1303             bool isStartNode = renderer->node() == &startContainer;
1304             bool isEndNode = renderer->node() == &endContainer;
1305             if (hasFlippedWritingMode != renderer->style().isFlippedBlocksWritingMode())
1306                 containsDifferentWritingModes = true;
1307             // FIXME: Sending 0 for the startOffset is a weird way of telling the renderer that the selection
1308             // doesn't start inside it, since we'll also send 0 if the selection *does* start in it, at offset 0.
1309             //
1310             // FIXME: Selection endpoints aren't always inside leaves, and we only build SelectionRects for leaves,
1311             // so we can't accurately determine which SelectionRects contain the selection start and end using
1312             // only the offsets of the start and end. We need to pass the whole Range.
1313             int beginSelectionOffset = isStartNode ? startOffset : 0;
1314             int endSelectionOffset = isEndNode ? endOffset : std::numeric_limits<int>::max();
1315             renderer->collectSelectionRects(newRects, beginSelectionOffset, endSelectionOffset);
1316             for (auto& selectionRect : newRects) {
1317                 if (selectionRect.containsStart() && !isStartNode)
1318                     selectionRect.setContainsStart(false);
1319                 if (selectionRect.containsEnd() && !isEndNode)
1320                     selectionRect.setContainsEnd(false);
1321                 if (selectionRect.logicalWidth() || selectionRect.logicalHeight())
1322                     rects.append(selectionRect);
1323             }
1324             newRects.shrink(0);
1325         }
1326     }
1327
1328     // The range could span over nodes with different writing modes.
1329     // If this is the case, we use the writing mode of the common ancestor.
1330     if (containsDifferentWritingModes) {
1331         if (Node* ancestor = commonAncestorContainer(&startContainer, &endContainer))
1332             hasFlippedWritingMode = ancestor->renderer()->style().isFlippedBlocksWritingMode();
1333     }
1334
1335     const size_t numberOfRects = rects.size();
1336
1337     // If the selection ends in a BR, then add the line break bit to the last
1338     // rect we have. This will cause its selection rect to extend to the
1339     // end of the line.
1340     if (stopNode && stopNode->hasTagName(HTMLNames::brTag) && numberOfRects) {
1341         // Only set the line break bit if the end of the range actually
1342         // extends all the way to include the <br>. VisiblePosition helps to
1343         // figure this out.
1344         VisiblePosition endPosition(createLegacyEditingPosition(&endContainer, endOffset), VP_DEFAULT_AFFINITY);
1345         VisiblePosition brPosition(createLegacyEditingPosition(stopNode, 0), VP_DEFAULT_AFFINITY);
1346         if (endPosition == brPosition)
1347             rects.last().setIsLineBreak(true);
1348     }
1349
1350     int lineTop = std::numeric_limits<int>::max();
1351     int lineBottom = std::numeric_limits<int>::min();
1352     int lastLineTop = lineTop;
1353     int lastLineBottom = lineBottom;
1354     int lineNumber = 0;
1355
1356     for (size_t i = 0; i < numberOfRects; ++i) {
1357         int currentRectTop = rects[i].logicalTop();
1358         int currentRectBottom = currentRectTop + rects[i].logicalHeight();
1359
1360         // We don't want to count the ruby text as a separate line.
1361         if (intervalsSufficientlyOverlap(currentRectTop, currentRectBottom, lineTop, lineBottom) || (i && rects[i].isRubyText())) {
1362             // Grow the current line bounds.
1363             lineTop = std::min(lineTop, currentRectTop);
1364             lineBottom = std::max(lineBottom, currentRectBottom);
1365             // Avoid overlap with the previous line.
1366             if (!hasFlippedWritingMode)
1367                 lineTop = std::max(lastLineBottom, lineTop);
1368             else
1369                 lineBottom = std::min(lastLineTop, lineBottom);
1370         } else {
1371             adjustLineHeightOfSelectionRects(rects, i, lineNumber, lineTop, lineBottom - lineTop);
1372             if (!hasFlippedWritingMode) {
1373                 lastLineTop = lineTop;
1374                 if (currentRectBottom >= lastLineTop) {
1375                     lastLineBottom = lineBottom;
1376                     lineTop = lastLineBottom;
1377                 } else {
1378                     lineTop = currentRectTop;
1379                     lastLineBottom = std::numeric_limits<int>::min();
1380                 }
1381                 lineBottom = currentRectBottom;
1382             } else {
1383                 lastLineBottom = lineBottom;
1384                 if (currentRectTop <= lastLineBottom && i && rects[i].pageNumber() == rects[i - 1].pageNumber()) {
1385                     lastLineTop = lineTop;
1386                     lineBottom = lastLineTop;
1387                 } else {
1388                     lastLineTop = std::numeric_limits<int>::max();
1389                     lineBottom = currentRectBottom;
1390                 }
1391                 lineTop = currentRectTop;
1392             }
1393             ++lineNumber;
1394         }
1395     }
1396
1397     // Adjust line height.
1398     adjustLineHeightOfSelectionRects(rects, numberOfRects, lineNumber, lineTop, lineBottom - lineTop);
1399
1400     // Sort the rectangles and make sure there are no gaps. The rectangles could be unsorted when
1401     // there is ruby text and we could have gaps on the line when adjacent elements on the line
1402     // have a different orientation.
1403     size_t firstRectWithCurrentLineNumber = 0;
1404     for (size_t currentRect = 1; currentRect < numberOfRects; ++currentRect) {
1405         if (rects[currentRect].lineNumber() != rects[currentRect - 1].lineNumber()) {
1406             firstRectWithCurrentLineNumber = currentRect;
1407             continue;
1408         }
1409         if (rects[currentRect].logicalLeft() >= rects[currentRect - 1].logicalLeft())
1410             continue;
1411
1412         SelectionRect selectionRect = rects[currentRect];
1413         size_t i;
1414         for (i = currentRect; i > firstRectWithCurrentLineNumber && selectionRect.logicalLeft() < rects[i - 1].logicalLeft(); --i)
1415             rects[i] = rects[i - 1];
1416         rects[i] = selectionRect;
1417     }
1418
1419     for (size_t j = 1; j < numberOfRects; ++j) {
1420         if (rects[j].lineNumber() != rects[j - 1].lineNumber())
1421             continue;
1422         SelectionRect& previousRect = rects[j - 1];
1423         bool previousRectMayNotReachRightEdge = (previousRect.direction() == LTR && previousRect.containsEnd()) || (previousRect.direction() == RTL && previousRect.containsStart());
1424         if (previousRectMayNotReachRightEdge)
1425             continue;
1426         int adjustedWidth = rects[j].logicalLeft() - previousRect.logicalLeft();
1427         if (adjustedWidth > previousRect.logicalWidth())
1428             previousRect.setLogicalWidth(adjustedWidth);
1429     }
1430
1431     int maxLineNumber = lineNumber;
1432
1433     // Extend rects out to edges as needed.
1434     for (size_t i = 0; i < numberOfRects; ++i) {
1435         SelectionRect& selectionRect = rects[i];
1436         if (!selectionRect.isLineBreak() && selectionRect.lineNumber() >= maxLineNumber)
1437             continue;
1438         if (selectionRect.direction() == RTL && selectionRect.isFirstOnLine()) {
1439             selectionRect.setLogicalWidth(selectionRect.logicalWidth() + selectionRect.logicalLeft() - selectionRect.minX());
1440             selectionRect.setLogicalLeft(selectionRect.minX());
1441         } else if (selectionRect.direction() == LTR && selectionRect.isLastOnLine())
1442             selectionRect.setLogicalWidth(selectionRect.maxX() - selectionRect.logicalLeft());
1443     }
1444
1445     // Union all the rectangles on interior lines (i.e. not first or last).
1446     // On first and last lines, just avoid having overlaps by merging intersecting rectangles.
1447     Vector<SelectionRect> unionedRects;
1448     IntRect interiorUnionRect;
1449     for (size_t i = 0; i < numberOfRects; ++i) {
1450         SelectionRect& currentRect = rects[i];
1451         if (currentRect.lineNumber() == 1) {
1452             ASSERT(interiorUnionRect.isEmpty());
1453             if (!unionedRects.isEmpty()) {
1454                 SelectionRect& previousRect = unionedRects.last();
1455                 if (previousRect.rect().intersects(currentRect.rect())) {
1456                     previousRect = coalesceSelectionRects(currentRect, previousRect);
1457                     continue;
1458                 }
1459             }
1460             // Couldn't merge with previous rect, so just appending.
1461             unionedRects.append(currentRect);
1462         } else if (currentRect.lineNumber() < maxLineNumber) {
1463             if (interiorUnionRect.isEmpty()) {
1464                 // Start collecting interior rects.
1465                 interiorUnionRect = currentRect.rect();
1466             } else if (interiorUnionRect.intersects(currentRect.rect())
1467                 || interiorUnionRect.maxX() == currentRect.rect().x()
1468                 || interiorUnionRect.maxY() == currentRect.rect().y()
1469                 || interiorUnionRect.x() == currentRect.rect().maxX()
1470                 || interiorUnionRect.y() == currentRect.rect().maxY()) {
1471                 // Only union the lines that are attached.
1472                 // For iBooks, the interior lines may cross multiple horizontal pages.
1473                 interiorUnionRect.unite(currentRect.rect());
1474             } else {
1475                 unionedRects.append(SelectionRect(interiorUnionRect, currentRect.isHorizontal(), currentRect.pageNumber()));
1476                 interiorUnionRect = currentRect.rect();
1477             }
1478         } else {
1479             // Processing last line.
1480             if (!interiorUnionRect.isEmpty()) {
1481                 unionedRects.append(SelectionRect(interiorUnionRect, currentRect.isHorizontal(), currentRect.pageNumber()));
1482                 interiorUnionRect = IntRect();
1483             }
1484
1485             ASSERT(!unionedRects.isEmpty());
1486             SelectionRect& previousRect = unionedRects.last();
1487             if (previousRect.logicalTop() == currentRect.logicalTop() && previousRect.rect().intersects(currentRect.rect())) {
1488                 // previousRect is also on the last line, and intersects the current one.
1489                 previousRect = coalesceSelectionRects(currentRect, previousRect);
1490                 continue;
1491             }
1492             // Couldn't merge with previous rect, so just appending.
1493             unionedRects.append(currentRect);
1494         }
1495     }
1496
1497     rects.swap(unionedRects);
1498 }
1499 #endif
1500
1501 #if ENABLE(TREE_DEBUGGING)
1502 void Range::formatForDebugger(char* buffer, unsigned length) const
1503 {
1504     StringBuilder result;
1505
1506     const int FormatBufferSize = 1024;
1507     char s[FormatBufferSize];
1508     result.appendLiteral("from offset ");
1509     result.appendNumber(m_start.offset());
1510     result.appendLiteral(" of ");
1511     startContainer().formatForDebugger(s, FormatBufferSize);
1512     result.append(s);
1513     result.appendLiteral(" to offset ");
1514     result.appendNumber(m_end.offset());
1515     result.appendLiteral(" of ");
1516     endContainer().formatForDebugger(s, FormatBufferSize);
1517     result.append(s);
1518
1519     strncpy(buffer, result.toString().utf8().data(), length - 1);
1520 }
1521 #endif
1522
1523 bool Range::contains(const Range& other) const
1524 {
1525     if (commonAncestorContainer()->ownerDocument() != other.commonAncestorContainer()->ownerDocument())
1526         return false;
1527
1528     short startToStart = compareBoundaryPoints(Range::START_TO_START, &other, ASSERT_NO_EXCEPTION);
1529     if (startToStart > 0)
1530         return false;
1531
1532     short endToEnd = compareBoundaryPoints(Range::END_TO_END, &other, ASSERT_NO_EXCEPTION);
1533     return endToEnd >= 0;
1534 }
1535
1536 bool Range::contains(const VisiblePosition& position) const
1537 {
1538     RefPtr<Range> positionRange = makeRange(position, position);
1539     if (!positionRange)
1540         return false;
1541     return contains(*positionRange);
1542 }
1543
1544 bool areRangesEqual(const Range* a, const Range* b)
1545 {
1546     if (a == b)
1547         return true;
1548     if (!a || !b)
1549         return false;
1550     return a->startPosition() == b->startPosition() && a->endPosition() == b->endPosition();
1551 }
1552
1553 bool rangesOverlap(const Range* a, const Range* b)
1554 {
1555     if (!a || !b)
1556         return false;
1557
1558     if (a == b)
1559         return true;
1560
1561     if (a->commonAncestorContainer()->ownerDocument() != b->commonAncestorContainer()->ownerDocument())
1562         return false;
1563
1564     short startToStart = a->compareBoundaryPoints(Range::START_TO_START, b, ASSERT_NO_EXCEPTION);
1565     short endToEnd = a->compareBoundaryPoints(Range::END_TO_END, b, ASSERT_NO_EXCEPTION);
1566
1567     // First range contains the second range.
1568     if (startToStart <= 0 && endToEnd >= 0)
1569         return true;
1570
1571     // End of first range is inside second range.
1572     if (a->compareBoundaryPoints(Range::START_TO_END, b, ASSERT_NO_EXCEPTION) >= 0 && endToEnd <= 0)
1573         return true;
1574
1575     // Start of first range is inside second range.
1576     if (startToStart >= 0 && a->compareBoundaryPoints(Range::END_TO_START, b, ASSERT_NO_EXCEPTION) <= 0)
1577         return true;
1578
1579     return false;
1580 }
1581
1582 Ref<Range> rangeOfContents(Node& node)
1583 {
1584     Ref<Range> range = Range::create(node.document());
1585     int exception = 0;
1586     range->selectNodeContents(&node, exception);
1587     return range;
1588 }
1589
1590 static inline void boundaryNodeChildrenChanged(RangeBoundaryPoint& boundary, ContainerNode& container)
1591 {
1592     if (!boundary.childBefore())
1593         return;
1594     if (boundary.container() != &container)
1595         return;
1596     boundary.invalidateOffset();
1597 }
1598
1599 void Range::nodeChildrenChanged(ContainerNode& container)
1600 {
1601     ASSERT(&container.document() == &ownerDocument());
1602     boundaryNodeChildrenChanged(m_start, container);
1603     boundaryNodeChildrenChanged(m_end, container);
1604 }
1605
1606 static inline void boundaryNodeChildrenWillBeRemoved(RangeBoundaryPoint& boundary, ContainerNode& container)
1607 {
1608     for (Node* nodeToBeRemoved = container.firstChild(); nodeToBeRemoved; nodeToBeRemoved = nodeToBeRemoved->nextSibling()) {
1609         if (boundary.childBefore() == nodeToBeRemoved) {
1610             boundary.setToStartOfNode(&container);
1611             return;
1612         }
1613
1614         for (Node* n = boundary.container(); n; n = n->parentNode()) {
1615             if (n == nodeToBeRemoved) {
1616                 boundary.setToStartOfNode(&container);
1617                 return;
1618             }
1619         }
1620     }
1621 }
1622
1623 void Range::nodeChildrenWillBeRemoved(ContainerNode& container)
1624 {
1625     ASSERT(&container.document() == &ownerDocument());
1626     boundaryNodeChildrenWillBeRemoved(m_start, container);
1627     boundaryNodeChildrenWillBeRemoved(m_end, container);
1628 }
1629
1630 static inline void boundaryNodeWillBeRemoved(RangeBoundaryPoint& boundary, Node& nodeToBeRemoved)
1631 {
1632     if (boundary.childBefore() == &nodeToBeRemoved) {
1633         boundary.childBeforeWillBeRemoved();
1634         return;
1635     }
1636
1637     for (Node* n = boundary.container(); n; n = n->parentNode()) {
1638         if (n == &nodeToBeRemoved) {
1639             boundary.setToBeforeChild(nodeToBeRemoved);
1640             return;
1641         }
1642     }
1643 }
1644
1645 void Range::nodeWillBeRemoved(Node& node)
1646 {
1647     ASSERT(&node.document() == &ownerDocument());
1648     ASSERT(&node != &ownerDocument());
1649     ASSERT(node.parentNode());
1650     boundaryNodeWillBeRemoved(m_start, node);
1651     boundaryNodeWillBeRemoved(m_end, node);
1652 }
1653
1654 static inline void boundaryTextInserted(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
1655 {
1656     if (boundary.container() != text)
1657         return;
1658     unsigned boundaryOffset = boundary.offset();
1659     if (offset >= boundaryOffset)
1660         return;
1661     boundary.setOffset(boundaryOffset + length);
1662 }
1663
1664 void Range::textInserted(Node* text, unsigned offset, unsigned length)
1665 {
1666     ASSERT(text);
1667     ASSERT(&text->document() == &ownerDocument());
1668     boundaryTextInserted(m_start, text, offset, length);
1669     boundaryTextInserted(m_end, text, offset, length);
1670 }
1671
1672 static inline void boundaryTextRemoved(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
1673 {
1674     if (boundary.container() != text)
1675         return;
1676     unsigned boundaryOffset = boundary.offset();
1677     if (offset >= boundaryOffset)
1678         return;
1679     if (offset + length >= boundaryOffset)
1680         boundary.setOffset(offset);
1681     else
1682         boundary.setOffset(boundaryOffset - length);
1683 }
1684
1685 void Range::textRemoved(Node* text, unsigned offset, unsigned length)
1686 {
1687     ASSERT(text);
1688     ASSERT(&text->document() == &ownerDocument());
1689     boundaryTextRemoved(m_start, text, offset, length);
1690     boundaryTextRemoved(m_end, text, offset, length);
1691 }
1692
1693 static inline void boundaryTextNodesMerged(RangeBoundaryPoint& boundary, NodeWithIndex& oldNode, unsigned offset)
1694 {
1695     if (boundary.container() == oldNode.node())
1696         boundary.set(oldNode.node()->previousSibling(), boundary.offset() + offset, 0);
1697     else if (boundary.container() == oldNode.node()->parentNode() && boundary.offset() == oldNode.index())
1698         boundary.set(oldNode.node()->previousSibling(), offset, 0);
1699 }
1700
1701 void Range::textNodesMerged(NodeWithIndex& oldNode, unsigned offset)
1702 {
1703     ASSERT(oldNode.node());
1704     ASSERT(&oldNode.node()->document() == &ownerDocument());
1705     ASSERT(oldNode.node()->parentNode());
1706     ASSERT(oldNode.node()->isTextNode());
1707     ASSERT(oldNode.node()->previousSibling());
1708     ASSERT(oldNode.node()->previousSibling()->isTextNode());
1709     boundaryTextNodesMerged(m_start, oldNode, offset);
1710     boundaryTextNodesMerged(m_end, oldNode, offset);
1711 }
1712
1713 static inline void boundaryTextNodesSplit(RangeBoundaryPoint& boundary, Text* oldNode)
1714 {
1715     if (boundary.container() != oldNode)
1716         return;
1717     unsigned boundaryOffset = boundary.offset();
1718     if (boundaryOffset <= oldNode->length())
1719         return;
1720     boundary.set(oldNode->nextSibling(), boundaryOffset - oldNode->length(), 0);
1721 }
1722
1723 void Range::textNodeSplit(Text* oldNode)
1724 {
1725     ASSERT(oldNode);
1726     ASSERT(&oldNode->document() == &ownerDocument());
1727     ASSERT(oldNode->parentNode());
1728     ASSERT(oldNode->isTextNode());
1729     ASSERT(oldNode->nextSibling());
1730     ASSERT(oldNode->nextSibling()->isTextNode());
1731     boundaryTextNodesSplit(m_start, oldNode);
1732     boundaryTextNodesSplit(m_end, oldNode);
1733 }
1734
1735 void Range::expand(const String& unit, ExceptionCode& ec)
1736 {
1737     VisiblePosition start(startPosition());
1738     VisiblePosition end(endPosition());
1739     if (unit == "word") {
1740         start = startOfWord(start);
1741         end = endOfWord(end);
1742     } else if (unit == "sentence") {
1743         start = startOfSentence(start);
1744         end = endOfSentence(end);
1745     } else if (unit == "block") {
1746         start = startOfParagraph(start);
1747         end = endOfParagraph(end);
1748     } else if (unit == "document") {
1749         start = startOfDocument(start);
1750         end = endOfDocument(end);
1751     } else
1752         return;
1753     setStart(start.deepEquivalent().containerNode(), start.deepEquivalent().computeOffsetInContainerNode(), ec);
1754     setEnd(end.deepEquivalent().containerNode(), end.deepEquivalent().computeOffsetInContainerNode(), ec);
1755 }
1756
1757 Ref<ClientRectList> Range::getClientRects() const
1758 {
1759     ownerDocument().updateLayoutIgnorePendingStylesheets();
1760
1761     Vector<FloatQuad> quads;
1762     getBorderAndTextQuads(quads, CoordinateSpace::Client);
1763
1764     return ClientRectList::create(quads);
1765 }
1766
1767 Ref<ClientRect> Range::getBoundingClientRect() const
1768 {
1769     return ClientRect::create(boundingRectInternal(CoordinateSpace::Client));
1770 }
1771
1772 void Range::getBorderAndTextQuads(Vector<FloatQuad>& quads, CoordinateSpace space) const
1773 {
1774     Node* stopNode = pastLastNode();
1775
1776     HashSet<Node*> selectedElementsSet;
1777     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(*node)) {
1778         if (node->isElementNode())
1779             selectedElementsSet.add(node);
1780     }
1781
1782     // Don't include elements that are only partially selected.
1783     Node* lastNode = m_end.childBefore() ? m_end.childBefore() : &endContainer();
1784     for (Node* parent = lastNode->parentNode(); parent; parent = parent->parentNode())
1785         selectedElementsSet.remove(parent);
1786
1787     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(*node)) {
1788         if (is<Element>(*node) && selectedElementsSet.contains(node) && !selectedElementsSet.contains(node->parentNode())) {
1789             if (RenderBoxModelObject* renderBoxModelObject = downcast<Element>(*node).renderBoxModelObject()) {
1790                 Vector<FloatQuad> elementQuads;
1791                 renderBoxModelObject->absoluteQuads(elementQuads);
1792
1793                 if (space == CoordinateSpace::Client)
1794                     ownerDocument().adjustFloatQuadsForScrollAndAbsoluteZoomAndFrameScale(elementQuads, renderBoxModelObject->style());
1795
1796                 quads.appendVector(elementQuads);
1797             }
1798         } else if (is<Text>(*node)) {
1799             if (RenderText* renderText = downcast<Text>(*node).renderer()) {
1800                 int startOffset = node == &startContainer() ? m_start.offset() : 0;
1801                 int endOffset = node == &endContainer() ? m_end.offset() : INT_MAX;
1802
1803                 auto textQuads = renderText->absoluteQuadsForRange(startOffset, endOffset);
1804
1805                 if (space == CoordinateSpace::Client)
1806                     ownerDocument().adjustFloatQuadsForScrollAndAbsoluteZoomAndFrameScale(textQuads, renderText->style());
1807
1808                 quads.appendVector(textQuads);
1809             }
1810         }
1811     }
1812 }
1813
1814 FloatRect Range::boundingRectInternal(CoordinateSpace space) const
1815 {
1816     ownerDocument().updateLayoutIgnorePendingStylesheets();
1817
1818     Vector<FloatQuad> quads;
1819     getBorderAndTextQuads(quads, space);
1820
1821     FloatRect result;
1822     for (auto& quad : quads)
1823         result.unite(quad.boundingBox());
1824
1825     return result;
1826 }
1827
1828 FloatRect Range::absoluteBoundingRect() const
1829 {
1830     return boundingRectInternal(CoordinateSpace::Absolute);
1831 }
1832
1833 } // namespace WebCore
1834
1835 #if ENABLE(TREE_DEBUGGING)
1836
1837 void showTree(const WebCore::Range* range)
1838 {
1839     if (range && range->boundaryPointsValid()) {
1840         range->startContainer().showTreeAndMark(&range->startContainer(), "S", &range->endContainer(), "E");
1841         fprintf(stderr, "start offset: %d, end offset: %d\n", range->startOffset(), range->endOffset());
1842     }
1843 }
1844
1845 #endif