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