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