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