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

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