src/third_party/WebKit/Source/core/dom/Range.cpp

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