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