fda41661781885275fdbba62523d89c7656864fb
[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(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
77 PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument)
78 {
79     return adoptRef(new Range(ownerDocument));
80 }
81
82 inline 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
99 PassRefPtr<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
104 PassRefPtr<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
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 != &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
130 Node* 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
140 int 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
150 Node* 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
160 int 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
170 Node* 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
180 Node* 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
191 bool 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
201 static 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
213 void 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
242 void 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
271 void Range::setStart(const Position& start, ExceptionCode& ec)
272 {
273     Position parentAnchored = start.parentAnchoredEquivalent();
274     setStart(parentAnchored.containerNode(), parentAnchored.offsetInContainerNode(), ec);
275 }
276
277 void Range::setEnd(const Position& end, ExceptionCode& ec)
278 {
279     Position parentAnchored = end.parentAnchoredEquivalent();
280     setEnd(parentAnchored.containerNode(), parentAnchored.offsetInContainerNode(), ec);
281 }
282
283 void 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
296 bool 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
321 short 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
362 Range::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
409 short 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
460 short 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
553 short 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
558 bool Range::boundaryPointsValid() const
559 {
560     ExceptionCode ec = 0;
561     return m_start.container() && compareBoundaryPoints(m_start, m_end, ec) <= 0 && !ec;
562 }
563
564 void Range::deleteContents(ExceptionCode& ec)
565 {
566     checkDeleteExtract(ec);
567     if (ec)
568         return;
569
570     processContents(Delete, ec);
571 }
572
573 bool 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
614 static 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
627 static 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
647 static 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
672 PassRefPtr<DocumentFragment> Range::processContents(ActionType action, ExceptionCode& ec)
673 {
674     typedef Vector<RefPtr<Node> > NodeVector;
675
676     RefPtr<DocumentFragment> fragment;
677     if (action == Extract || action == Clone)
678         fragment = DocumentFragment::create(ownerDocument());
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     // Since mutation events can modify the range during the process, the boundary points need to be saved.
697     RangeBoundaryPoint originalStart(m_start);
698     RangeBoundaryPoint originalEnd(m_end);
699
700     // what is the highest node that partially selects the start / end of the range?
701     RefPtr<Node> partialStart = highestAncestorUnderCommonRoot(originalStart.container(), commonRoot.get());
702     RefPtr<Node> partialEnd = highestAncestorUnderCommonRoot(originalEnd.container(), commonRoot.get());
703
704     // Start and end containers are different.
705     // There are three possibilities here:
706     // 1. Start container == commonRoot (End container must be a descendant)
707     // 2. End container == commonRoot (Start container must be a descendant)
708     // 3. Neither is commonRoot, they are both descendants
709     //
710     // In case 3, we grab everything after the start (up until a direct child
711     // of commonRoot) into leftContents, and everything before the end (up until
712     // a direct child of commonRoot) into rightContents. Then we process all
713     // commonRoot children between leftContents and rightContents
714     //
715     // In case 1 or 2, we skip either processing of leftContents or rightContents,
716     // in which case the last lot of nodes either goes from the first or last
717     // child of commonRoot.
718     //
719     // These are deleted, cloned, or extracted (i.e. both) depending on action.
720
721     // Note that we are verifying that our common root hierarchy is still intact
722     // after any DOM mutation event, at various stages below. See webkit bug 60350.
723
724     RefPtr<Node> leftContents;
725     if (originalStart.container() != commonRoot && commonRoot->contains(originalStart.container())) {
726         leftContents = processContentsBetweenOffsets(action, 0, originalStart.container(), originalStart.offset(), lengthOfContentsInNode(originalStart.container()), ec);
727         leftContents = processAncestorsAndTheirSiblings(action, originalStart.container(), ProcessContentsForward, leftContents, commonRoot.get(), ec);
728     }
729
730     RefPtr<Node> rightContents;
731     if (m_end.container() != commonRoot && commonRoot->contains(originalEnd.container())) {
732         rightContents = processContentsBetweenOffsets(action, 0, originalEnd.container(), 0, originalEnd.offset(), ec);
733         rightContents = processAncestorsAndTheirSiblings(action, originalEnd.container(), ProcessContentsBackward, rightContents, commonRoot.get(), ec);
734     }
735
736     // delete all children of commonRoot between the start and end container
737     RefPtr<Node> processStart = childOfCommonRootBeforeOffset(originalStart.container(), originalStart.offset(), commonRoot.get());
738     if (processStart && originalStart.container() != commonRoot) // processStart contains nodes before m_start.
739         processStart = processStart->nextSibling();
740     RefPtr<Node> processEnd = childOfCommonRootBeforeOffset(originalEnd.container(), originalEnd.offset(), commonRoot.get());
741
742     // Collapse the range, making sure that the result is not within a node that was partially selected.
743     if (action == Extract || action == Delete) {
744         if (partialStart && commonRoot->contains(partialStart.get()))
745             setStart(partialStart->parentNode(), partialStart->nodeIndex() + 1, ec);
746         else if (partialEnd && commonRoot->contains(partialEnd.get()))
747             setStart(partialEnd->parentNode(), partialEnd->nodeIndex(), ec);
748         if (ec)
749             return 0;
750         m_end = m_start;
751     }
752
753     // Now add leftContents, stuff in between, and rightContents to the fragment
754     // (or just delete the stuff in between)
755
756     if ((action == Extract || action == Clone) && leftContents)
757         fragment->appendChild(leftContents, ec);
758
759     if (processStart) {
760         NodeVector nodes;
761         for (Node* n = processStart.get(); n && n != processEnd; n = n->nextSibling())
762             nodes.append(n);
763         processNodes(action, nodes, commonRoot, fragment, ec);
764     }
765
766     if ((action == Extract || action == Clone) && rightContents)
767         fragment->appendChild(rightContents, ec);
768
769     return fragment.release();
770 }
771
772 static inline void deleteCharacterData(PassRefPtr<CharacterData> data, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
773 {
774     if (data->length() - endOffset)
775         data->deleteData(endOffset, data->length() - endOffset, ec);
776     if (startOffset)
777         data->deleteData(0, startOffset, ec);
778 }
779
780 PassRefPtr<Node> Range::processContentsBetweenOffsets(ActionType action, PassRefPtr<DocumentFragment> fragment,
781     Node* container, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
782 {
783     ASSERT(container);
784     ASSERT(startOffset <= endOffset);
785
786     // This switch statement must be consistent with that of lengthOfContentsInNode.
787     RefPtr<Node> result;   
788     switch (container->nodeType()) {
789     case Node::TEXT_NODE:
790     case Node::CDATA_SECTION_NODE:
791     case Node::COMMENT_NODE:
792         ASSERT(endOffset <= static_cast<CharacterData*>(container)->length());
793         if (action == Extract || action == Clone) {
794             RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(container->cloneNode(true));
795             deleteCharacterData(c, startOffset, endOffset, ec);
796             if (fragment) {
797                 result = fragment;
798                 result->appendChild(c.release(), ec);
799             } else
800                 result = c.release();
801         }
802         if (action == Extract || action == Delete)
803             static_cast<CharacterData*>(container)->deleteData(startOffset, endOffset - startOffset, ec);
804         break;
805     case Node::PROCESSING_INSTRUCTION_NODE:
806         ASSERT(endOffset <= static_cast<ProcessingInstruction*>(container)->data().length());
807         if (action == Extract || action == Clone) {
808             RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(container->cloneNode(true));
809             c->setData(c->data().substring(startOffset, endOffset - startOffset), ec);
810             if (fragment) {
811                 result = fragment;
812                 result->appendChild(c.release(), ec);
813             } else
814                 result = c.release();
815         }
816         if (action == Extract || action == Delete) {
817             ProcessingInstruction* pi = static_cast<ProcessingInstruction*>(container);
818             String data(pi->data());
819             data.remove(startOffset, endOffset - startOffset);
820             pi->setData(data, ec);
821         }
822         break;
823     case Node::ELEMENT_NODE:
824     case Node::ATTRIBUTE_NODE:
825     case Node::ENTITY_REFERENCE_NODE:
826     case Node::ENTITY_NODE:
827     case Node::DOCUMENT_NODE:
828     case Node::DOCUMENT_TYPE_NODE:
829     case Node::DOCUMENT_FRAGMENT_NODE:
830     case Node::NOTATION_NODE:
831     case Node::XPATH_NAMESPACE_NODE:
832         // FIXME: Should we assert that some nodes never appear here?
833         if (action == Extract || action == Clone) {
834             if (fragment)
835                 result = fragment;
836             else
837                 result = container->cloneNode(false);
838         }
839
840         Node* n = container->firstChild();
841         Vector<RefPtr<Node> > nodes;
842         for (unsigned i = startOffset; n && i; i--)
843             n = n->nextSibling();
844         for (unsigned i = startOffset; n && i < endOffset; i++, n = n->nextSibling())
845             nodes.append(n);
846
847         processNodes(action, nodes, container, result, ec);
848         break;
849     }
850
851     return result.release();
852 }
853
854 void Range::processNodes(ActionType action, Vector<RefPtr<Node> >& nodes, PassRefPtr<Node> oldContainer, PassRefPtr<Node> newContainer, ExceptionCode& ec)
855 {
856     for (unsigned i = 0; i < nodes.size(); i++) {
857         switch (action) {
858         case Delete:
859             oldContainer->removeChild(nodes[i].get(), ec);
860             break;
861         case Extract:
862             newContainer->appendChild(nodes[i].release(), ec); // will remove n from its parent
863             break;
864         case Clone:
865             newContainer->appendChild(nodes[i]->cloneNode(true), ec);
866             break;
867         }
868     }
869 }
870
871 PassRefPtr<Node> Range::processAncestorsAndTheirSiblings(ActionType action, Node* container, ContentsProcessDirection direction, PassRefPtr<Node> passedClonedContainer, Node* commonRoot, ExceptionCode& ec)
872 {
873     typedef Vector<RefPtr<Node> > NodeVector;
874
875     RefPtr<Node> clonedContainer = passedClonedContainer;
876     Vector<RefPtr<Node> > ancestors;
877     for (ContainerNode* n = container->parentNode(); n && n != commonRoot; n = n->parentNode())
878         ancestors.append(n);
879
880     RefPtr<Node> firstChildInAncestorToProcess = direction == ProcessContentsForward ? container->nextSibling() : container->previousSibling();
881     for (Vector<RefPtr<Node> >::const_iterator it = ancestors.begin(); it != ancestors.end(); ++it) {
882         RefPtr<Node> ancestor = *it;
883         if (action == Extract || action == Clone) {
884             if (RefPtr<Node> clonedAncestor = ancestor->cloneNode(false)) { // Might have been removed already during mutation event.
885                 clonedAncestor->appendChild(clonedContainer, ec);
886                 clonedContainer = clonedAncestor;
887             }
888         }
889
890         // Copy siblings of an ancestor of start/end containers
891         // FIXME: This assertion may fail if DOM is modified during mutation event
892         // FIXME: Share code with Range::processNodes
893         ASSERT(!firstChildInAncestorToProcess || firstChildInAncestorToProcess->parentNode() == ancestor);
894         
895         NodeVector nodes;
896         for (Node* child = firstChildInAncestorToProcess.get(); child;
897             child = (direction == ProcessContentsForward) ? child->nextSibling() : child->previousSibling())
898             nodes.append(child);
899
900         for (NodeVector::const_iterator it = nodes.begin(); it != nodes.end(); ++it) {
901             Node* child = it->get();
902             switch (action) {
903             case Delete:
904                 ancestor->removeChild(child, ec);
905                 break;
906             case Extract: // will remove child from ancestor
907                 if (direction == ProcessContentsForward)
908                     clonedContainer->appendChild(child, ec);
909                 else
910                     clonedContainer->insertBefore(child, clonedContainer->firstChild(), ec);
911                 break;
912             case Clone:
913                 if (direction == ProcessContentsForward)
914                     clonedContainer->appendChild(child->cloneNode(true), ec);
915                 else
916                     clonedContainer->insertBefore(child->cloneNode(true), clonedContainer->firstChild(), ec);
917                 break;
918             }
919         }
920         firstChildInAncestorToProcess = direction == ProcessContentsForward ? ancestor->nextSibling() : ancestor->previousSibling();
921     }
922
923     return clonedContainer.release();
924 }
925
926 PassRefPtr<DocumentFragment> Range::extractContents(ExceptionCode& ec)
927 {
928     checkDeleteExtract(ec);
929     if (ec)
930         return 0;
931
932     return processContents(Extract, ec);
933 }
934
935 PassRefPtr<DocumentFragment> Range::cloneContents(ExceptionCode& ec)
936 {
937     if (!m_start.container()) {
938         ec = INVALID_STATE_ERR;
939         return 0;
940     }
941
942     return processContents(Clone, ec);
943 }
944
945 void Range::insertNode(PassRefPtr<Node> prpNewNode, ExceptionCode& ec)
946 {
947     RefPtr<Node> newNode = prpNewNode;
948
949     ec = 0;
950
951     if (!m_start.container()) {
952         ec = INVALID_STATE_ERR;
953         return;
954     }
955
956     if (!newNode) {
957         ec = NOT_FOUND_ERR;
958         return;
959     }
960
961     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
962     // the Range is read-only.
963     if (containedByReadOnly()) {
964         ec = NO_MODIFICATION_ALLOWED_ERR;
965         return;
966     }
967
968     // HIERARCHY_REQUEST_ERR: Raised if the container of the start of the Range is of a type that
969     // does not allow children of the type of newNode or if newNode is an ancestor of the container.
970
971     // an extra one here - if a text node is going to split, it must have a parent to insert into
972     bool startIsText = m_start.container()->isTextNode();
973     if (startIsText && !m_start.container()->parentNode()) {
974         ec = HIERARCHY_REQUEST_ERR;
975         return;
976     }
977
978     // In the case where the container is a text node, we check against the container's parent, because
979     // text nodes get split up upon insertion.
980     Node* checkAgainst;
981     if (startIsText)
982         checkAgainst = m_start.container()->parentNode();
983     else
984         checkAgainst = m_start.container();
985
986     Node::NodeType newNodeType = newNode->nodeType();
987     int numNewChildren;
988     if (newNodeType == Node::DOCUMENT_FRAGMENT_NODE && !newNode->isShadowRoot()) {
989         // check each child node, not the DocumentFragment itself
990         numNewChildren = 0;
991         for (Node* c = newNode->firstChild(); c; c = c->nextSibling()) {
992             if (!checkAgainst->childTypeAllowed(c->nodeType())) {
993                 ec = HIERARCHY_REQUEST_ERR;
994                 return;
995             }
996             ++numNewChildren;
997         }
998     } else {
999         numNewChildren = 1;
1000         if (!checkAgainst->childTypeAllowed(newNodeType)) {
1001             ec = HIERARCHY_REQUEST_ERR;
1002             return;
1003         }
1004     }
1005
1006     for (Node* n = m_start.container(); n; n = n->parentNode()) {
1007         if (n == newNode) {
1008             ec = HIERARCHY_REQUEST_ERR;
1009             return;
1010         }
1011     }
1012
1013     // INVALID_NODE_TYPE_ERR: Raised if newNode is an Attr, Entity, Notation, ShadowRoot or Document node.
1014     switch (newNodeType) {
1015     case Node::ATTRIBUTE_NODE:
1016     case Node::ENTITY_NODE:
1017     case Node::NOTATION_NODE:
1018     case Node::DOCUMENT_NODE:
1019         ec = RangeException::INVALID_NODE_TYPE_ERR;
1020         return;
1021     default:
1022         if (newNode->isShadowRoot()) {
1023             ec = RangeException::INVALID_NODE_TYPE_ERR;
1024             return;
1025         }
1026         break;
1027     }
1028
1029     EventQueueScope scope;
1030     bool collapsed = m_start == m_end;
1031     RefPtr<Node> container;
1032     if (startIsText) {
1033         container = m_start.container();
1034         RefPtr<Text> newText = toText(container.get())->splitText(m_start.offset(), ec);
1035         if (ec)
1036             return;
1037         
1038         container = m_start.container();
1039         container->parentNode()->insertBefore(newNode.release(), newText.get(), ec);
1040         if (ec)
1041             return;
1042
1043         if (collapsed)
1044             m_end.setToBeforeChild(newText.get());
1045     } else {
1046         RefPtr<Node> lastChild;
1047         if (collapsed)
1048             lastChild = (newNodeType == Node::DOCUMENT_FRAGMENT_NODE) ? newNode->lastChild() : newNode;
1049
1050         int startOffset = m_start.offset();
1051         container = m_start.container();
1052         container->insertBefore(newNode.release(), container->childNode(startOffset), ec);
1053         if (ec)
1054             return;
1055
1056         if (collapsed && numNewChildren)
1057             m_end.set(m_start.container(), startOffset + numNewChildren, lastChild.get());
1058     }
1059 }
1060
1061 String Range::toString(ExceptionCode& ec) const
1062 {
1063     if (!m_start.container()) {
1064         ec = INVALID_STATE_ERR;
1065         return String();
1066     }
1067
1068     StringBuilder builder;
1069
1070     Node* pastLast = pastLastNode();
1071     for (Node* n = firstNode(); n != pastLast; n = NodeTraversal::next(n)) {
1072         if (n->nodeType() == Node::TEXT_NODE || n->nodeType() == Node::CDATA_SECTION_NODE) {
1073             const String& data = static_cast<CharacterData*>(n)->data();
1074             int length = data.length();
1075             int start = (n == m_start.container()) ? min(max(0, m_start.offset()), length) : 0;
1076             int end = (n == m_end.container()) ? min(max(start, m_end.offset()), length) : length;
1077             builder.append(data, start, end - start);
1078         }
1079     }
1080
1081     return builder.toString();
1082 }
1083
1084 String Range::toHTML() const
1085 {
1086     return createMarkup(*this);
1087 }
1088
1089 String Range::text() const
1090 {
1091     if (!m_start.container())
1092         return String();
1093
1094     // We need to update layout, since plainText uses line boxes in the render tree.
1095     // FIXME: As with innerText, we'd like this to work even if there are no render objects.
1096     m_start.container()->document().updateLayout();
1097
1098     return plainText(this);
1099 }
1100
1101 PassRefPtr<DocumentFragment> Range::createContextualFragment(const String& markup, ExceptionCode& ec)
1102 {
1103     if (!m_start.container()) {
1104         ec = INVALID_STATE_ERR;
1105         return 0;
1106     }
1107
1108     Node* element = m_start.container()->isElementNode() ? m_start.container() : m_start.container()->parentNode();
1109     if (!element || !element->isHTMLElement()) {
1110         ec = NOT_SUPPORTED_ERR;
1111         return 0;
1112     }
1113
1114     RefPtr<DocumentFragment> fragment = WebCore::createContextualFragment(markup, toHTMLElement(element), AllowScriptingContentAndDoNotMarkAlreadyStarted, ec);
1115     if (!fragment)
1116         return 0;
1117
1118     return fragment.release();
1119 }
1120
1121
1122 void Range::detach(ExceptionCode& ec)
1123 {
1124     // Check first to see if we've already detached:
1125     if (!m_start.container()) {
1126         ec = INVALID_STATE_ERR;
1127         return;
1128     }
1129
1130     m_ownerDocument->detachRange(this);
1131
1132     m_start.clear();
1133     m_end.clear();
1134 }
1135
1136 Node* Range::checkNodeWOffset(Node* n, int offset, ExceptionCode& ec) const
1137 {
1138     switch (n->nodeType()) {
1139         case Node::DOCUMENT_TYPE_NODE:
1140         case Node::ENTITY_NODE:
1141         case Node::NOTATION_NODE:
1142             ec = RangeException::INVALID_NODE_TYPE_ERR;
1143             return 0;
1144         case Node::CDATA_SECTION_NODE:
1145         case Node::COMMENT_NODE:
1146         case Node::TEXT_NODE:
1147             if (static_cast<unsigned>(offset) > static_cast<CharacterData*>(n)->length())
1148                 ec = INDEX_SIZE_ERR;
1149             return 0;
1150         case Node::PROCESSING_INSTRUCTION_NODE:
1151             if (static_cast<unsigned>(offset) > static_cast<ProcessingInstruction*>(n)->data().length())
1152                 ec = INDEX_SIZE_ERR;
1153             return 0;
1154         case Node::ATTRIBUTE_NODE:
1155         case Node::DOCUMENT_FRAGMENT_NODE:
1156         case Node::DOCUMENT_NODE:
1157         case Node::ELEMENT_NODE:
1158         case Node::ENTITY_REFERENCE_NODE:
1159         case Node::XPATH_NAMESPACE_NODE: {
1160             if (!offset)
1161                 return 0;
1162             Node* childBefore = n->childNode(offset - 1);
1163             if (!childBefore)
1164                 ec = INDEX_SIZE_ERR;
1165             return childBefore;
1166         }
1167     }
1168     ASSERT_NOT_REACHED();
1169     return 0;
1170 }
1171
1172 void Range::checkNodeBA(Node* n, ExceptionCode& ec) const
1173 {
1174     // INVALID_NODE_TYPE_ERR: Raised if the root container of refNode is not an
1175     // Attr, Document, DocumentFragment or ShadowRoot node, or part of a SVG shadow DOM tree,
1176     // or if refNode is a Document, DocumentFragment, ShadowRoot, Attr, Entity, or Notation node.
1177
1178     switch (n->nodeType()) {
1179         case Node::ATTRIBUTE_NODE:
1180         case Node::DOCUMENT_FRAGMENT_NODE:
1181         case Node::DOCUMENT_NODE:
1182         case Node::ENTITY_NODE:
1183         case Node::NOTATION_NODE:
1184             ec = RangeException::INVALID_NODE_TYPE_ERR;
1185             return;
1186         case Node::CDATA_SECTION_NODE:
1187         case Node::COMMENT_NODE:
1188         case Node::DOCUMENT_TYPE_NODE:
1189         case Node::ELEMENT_NODE:
1190         case Node::ENTITY_REFERENCE_NODE:
1191         case Node::PROCESSING_INSTRUCTION_NODE:
1192         case Node::TEXT_NODE:
1193         case Node::XPATH_NAMESPACE_NODE:
1194             break;
1195     }
1196
1197     Node* root = n;
1198     while (ContainerNode* parent = root->parentNode())
1199         root = parent;
1200
1201     switch (root->nodeType()) {
1202         case Node::ATTRIBUTE_NODE:
1203         case Node::DOCUMENT_NODE:
1204         case Node::DOCUMENT_FRAGMENT_NODE:
1205             break;
1206         case Node::CDATA_SECTION_NODE:
1207         case Node::COMMENT_NODE:
1208         case Node::DOCUMENT_TYPE_NODE:
1209         case Node::ELEMENT_NODE:
1210         case Node::ENTITY_NODE:
1211         case Node::ENTITY_REFERENCE_NODE:
1212         case Node::NOTATION_NODE:
1213         case Node::PROCESSING_INSTRUCTION_NODE:
1214         case Node::TEXT_NODE:
1215         case Node::XPATH_NAMESPACE_NODE:
1216             ec = RangeException::INVALID_NODE_TYPE_ERR;
1217             return;
1218     }
1219 }
1220
1221 PassRefPtr<Range> Range::cloneRange(ExceptionCode& ec) const
1222 {
1223     if (!m_start.container()) {
1224         ec = INVALID_STATE_ERR;
1225         return 0;
1226     }
1227
1228     return Range::create(m_ownerDocument, m_start.container(), m_start.offset(), m_end.container(), m_end.offset());
1229 }
1230
1231 void Range::setStartAfter(Node* refNode, ExceptionCode& ec)
1232 {
1233     if (!m_start.container()) {
1234         ec = INVALID_STATE_ERR;
1235         return;
1236     }
1237
1238     if (!refNode) {
1239         ec = NOT_FOUND_ERR;
1240         return;
1241     }
1242
1243     ec = 0;
1244     checkNodeBA(refNode, ec);
1245     if (ec)
1246         return;
1247
1248     setStart(refNode->parentNode(), refNode->nodeIndex() + 1, ec);
1249 }
1250
1251 void Range::setEndBefore(Node* refNode, ExceptionCode& ec)
1252 {
1253     if (!m_start.container()) {
1254         ec = INVALID_STATE_ERR;
1255         return;
1256     }
1257
1258     if (!refNode) {
1259         ec = NOT_FOUND_ERR;
1260         return;
1261     }
1262
1263     ec = 0;
1264     checkNodeBA(refNode, ec);
1265     if (ec)
1266         return;
1267
1268     setEnd(refNode->parentNode(), refNode->nodeIndex(), ec);
1269 }
1270
1271 void Range::setEndAfter(Node* refNode, ExceptionCode& ec)
1272 {
1273     if (!m_start.container()) {
1274         ec = INVALID_STATE_ERR;
1275         return;
1276     }
1277
1278     if (!refNode) {
1279         ec = NOT_FOUND_ERR;
1280         return;
1281     }
1282
1283     ec = 0;
1284     checkNodeBA(refNode, ec);
1285     if (ec)
1286         return;
1287
1288     setEnd(refNode->parentNode(), refNode->nodeIndex() + 1, ec);
1289 }
1290
1291 void Range::selectNode(Node* refNode, ExceptionCode& ec)
1292 {
1293     if (!m_start.container()) {
1294         ec = INVALID_STATE_ERR;
1295         return;
1296     }
1297
1298     if (!refNode) {
1299         ec = NOT_FOUND_ERR;
1300         return;
1301     }
1302
1303     // INVALID_NODE_TYPE_ERR: Raised if an ancestor of refNode is an Entity, Notation or
1304     // DocumentType node or if refNode is a Document, DocumentFragment, ShadowRoot, Attr, Entity, or Notation
1305     // node.
1306     for (ContainerNode* anc = refNode->parentNode(); anc; anc = anc->parentNode()) {
1307         switch (anc->nodeType()) {
1308             case Node::ATTRIBUTE_NODE:
1309             case Node::CDATA_SECTION_NODE:
1310             case Node::COMMENT_NODE:
1311             case Node::DOCUMENT_FRAGMENT_NODE:
1312             case Node::DOCUMENT_NODE:
1313             case Node::ELEMENT_NODE:
1314             case Node::ENTITY_REFERENCE_NODE:
1315             case Node::PROCESSING_INSTRUCTION_NODE:
1316             case Node::TEXT_NODE:
1317             case Node::XPATH_NAMESPACE_NODE:
1318                 break;
1319             case Node::DOCUMENT_TYPE_NODE:
1320             case Node::ENTITY_NODE:
1321             case Node::NOTATION_NODE:
1322                 ec = RangeException::INVALID_NODE_TYPE_ERR;
1323                 return;
1324         }
1325     }
1326
1327     switch (refNode->nodeType()) {
1328         case Node::CDATA_SECTION_NODE:
1329         case Node::COMMENT_NODE:
1330         case Node::DOCUMENT_TYPE_NODE:
1331         case Node::ELEMENT_NODE:
1332         case Node::ENTITY_REFERENCE_NODE:
1333         case Node::PROCESSING_INSTRUCTION_NODE:
1334         case Node::TEXT_NODE:
1335         case Node::XPATH_NAMESPACE_NODE:
1336             break;
1337         case Node::ATTRIBUTE_NODE:
1338         case Node::DOCUMENT_FRAGMENT_NODE:
1339         case Node::DOCUMENT_NODE:
1340         case Node::ENTITY_NODE:
1341         case Node::NOTATION_NODE:
1342             ec = RangeException::INVALID_NODE_TYPE_ERR;
1343             return;
1344     }
1345
1346     if (m_ownerDocument != &refNode->document())
1347         setDocument(refNode->document());
1348
1349     ec = 0;
1350     setStartBefore(refNode, ec);
1351     if (ec)
1352         return;
1353     setEndAfter(refNode, ec);
1354 }
1355
1356 void Range::selectNodeContents(Node* refNode, ExceptionCode& ec)
1357 {
1358     if (!m_start.container()) {
1359         ec = INVALID_STATE_ERR;
1360         return;
1361     }
1362
1363     if (!refNode) {
1364         ec = NOT_FOUND_ERR;
1365         return;
1366     }
1367
1368     // INVALID_NODE_TYPE_ERR: Raised if refNode or an ancestor of refNode is an Entity, Notation
1369     // or DocumentType node.
1370     for (Node* n = refNode; n; n = n->parentNode()) {
1371         switch (n->nodeType()) {
1372             case Node::ATTRIBUTE_NODE:
1373             case Node::CDATA_SECTION_NODE:
1374             case Node::COMMENT_NODE:
1375             case Node::DOCUMENT_FRAGMENT_NODE:
1376             case Node::DOCUMENT_NODE:
1377             case Node::ELEMENT_NODE:
1378             case Node::ENTITY_REFERENCE_NODE:
1379             case Node::PROCESSING_INSTRUCTION_NODE:
1380             case Node::TEXT_NODE:
1381             case Node::XPATH_NAMESPACE_NODE:
1382                 break;
1383             case Node::DOCUMENT_TYPE_NODE:
1384             case Node::ENTITY_NODE:
1385             case Node::NOTATION_NODE:
1386                 ec = RangeException::INVALID_NODE_TYPE_ERR;
1387                 return;
1388         }
1389     }
1390
1391     if (m_ownerDocument != &refNode->document())
1392         setDocument(refNode->document());
1393
1394     m_start.setToStartOfNode(refNode);
1395     m_end.setToEndOfNode(refNode);
1396 }
1397
1398 void Range::surroundContents(PassRefPtr<Node> passNewParent, ExceptionCode& ec)
1399 {
1400     RefPtr<Node> newParent = passNewParent;
1401
1402     if (!m_start.container()) {
1403         ec = INVALID_STATE_ERR;
1404         return;
1405     }
1406
1407     if (!newParent) {
1408         ec = NOT_FOUND_ERR;
1409         return;
1410     }
1411
1412     // INVALID_NODE_TYPE_ERR: Raised if node is an Attr, Entity, DocumentType, Notation,
1413     // Document, or DocumentFragment node.
1414     switch (newParent->nodeType()) {
1415         case Node::ATTRIBUTE_NODE:
1416         case Node::DOCUMENT_FRAGMENT_NODE:
1417         case Node::DOCUMENT_NODE:
1418         case Node::DOCUMENT_TYPE_NODE:
1419         case Node::ENTITY_NODE:
1420         case Node::NOTATION_NODE:
1421             ec = RangeException::INVALID_NODE_TYPE_ERR;
1422             return;
1423         case Node::CDATA_SECTION_NODE:
1424         case Node::COMMENT_NODE:
1425         case Node::ELEMENT_NODE:
1426         case Node::ENTITY_REFERENCE_NODE:
1427         case Node::PROCESSING_INSTRUCTION_NODE:
1428         case Node::TEXT_NODE:
1429         case Node::XPATH_NAMESPACE_NODE:
1430             break;
1431     }
1432
1433     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
1434     // the Range is read-only.
1435     if (containedByReadOnly()) {
1436         ec = NO_MODIFICATION_ALLOWED_ERR;
1437         return;
1438     }
1439
1440     // Raise a HIERARCHY_REQUEST_ERR if m_start.container() doesn't accept children like newParent.
1441     Node* parentOfNewParent = m_start.container();
1442
1443     // If m_start.container() is a character data node, it will be split and it will be its parent that will 
1444     // need to accept newParent (or in the case of a comment, it logically "would" be inserted into the parent,
1445     // although this will fail below for another reason).
1446     if (parentOfNewParent->isCharacterDataNode())
1447         parentOfNewParent = parentOfNewParent->parentNode();
1448     if (!parentOfNewParent || !parentOfNewParent->childTypeAllowed(newParent->nodeType())) {
1449         ec = HIERARCHY_REQUEST_ERR;
1450         return;
1451     }
1452     
1453     if (newParent->contains(m_start.container())) {
1454         ec = HIERARCHY_REQUEST_ERR;
1455         return;
1456     }
1457
1458     // FIXME: Do we need a check if the node would end up with a child node of a type not
1459     // allowed by the type of node?
1460
1461     // BAD_BOUNDARYPOINTS_ERR: Raised if the Range partially selects a non-Text node.
1462     Node* startNonTextContainer = m_start.container();
1463     if (startNonTextContainer->nodeType() == Node::TEXT_NODE)
1464         startNonTextContainer = startNonTextContainer->parentNode();
1465     Node* endNonTextContainer = m_end.container();
1466     if (endNonTextContainer->nodeType() == Node::TEXT_NODE)
1467         endNonTextContainer = endNonTextContainer->parentNode();
1468     if (startNonTextContainer != endNonTextContainer) {
1469         ec = RangeException::BAD_BOUNDARYPOINTS_ERR;
1470         return;
1471     }
1472
1473     ec = 0;
1474     while (Node* n = newParent->firstChild()) {
1475         toContainerNode(newParent.get())->removeChild(n, ec);
1476         if (ec)
1477             return;
1478     }
1479     RefPtr<DocumentFragment> fragment = extractContents(ec);
1480     if (ec)
1481         return;
1482     insertNode(newParent, ec);
1483     if (ec)
1484         return;
1485     newParent->appendChild(fragment.release(), ec);
1486     if (ec)
1487         return;
1488     selectNode(newParent.get(), ec);
1489 }
1490
1491 void Range::setStartBefore(Node* refNode, ExceptionCode& ec)
1492 {
1493     if (!m_start.container()) {
1494         ec = INVALID_STATE_ERR;
1495         return;
1496     }
1497
1498     if (!refNode) {
1499         ec = NOT_FOUND_ERR;
1500         return;
1501     }
1502
1503     ec = 0;
1504     checkNodeBA(refNode, ec);
1505     if (ec)
1506         return;
1507
1508     setStart(refNode->parentNode(), refNode->nodeIndex(), ec);
1509 }
1510
1511 void Range::checkDeleteExtract(ExceptionCode& ec)
1512 {
1513     if (!m_start.container()) {
1514         ec = INVALID_STATE_ERR;
1515         return;
1516     }
1517
1518     ec = 0;
1519     if (!commonAncestorContainer(ec) || ec)
1520         return;
1521         
1522     Node* pastLast = pastLastNode();
1523     for (Node* n = firstNode(); n != pastLast; n = NodeTraversal::next(n)) {
1524         if (n->isReadOnlyNode()) {
1525             ec = NO_MODIFICATION_ALLOWED_ERR;
1526             return;
1527         }
1528         if (n->nodeType() == Node::DOCUMENT_TYPE_NODE) {
1529             ec = HIERARCHY_REQUEST_ERR;
1530             return;
1531         }
1532     }
1533
1534     if (containedByReadOnly()) {
1535         ec = NO_MODIFICATION_ALLOWED_ERR;
1536         return;
1537     }
1538 }
1539
1540 bool Range::containedByReadOnly() const
1541 {
1542     for (Node* n = m_start.container(); n; n = n->parentNode()) {
1543         if (n->isReadOnlyNode())
1544             return true;
1545     }
1546     for (Node* n = m_end.container(); n; n = n->parentNode()) {
1547         if (n->isReadOnlyNode())
1548             return true;
1549     }
1550     return false;
1551 }
1552
1553 Node* Range::firstNode() const
1554 {
1555     if (!m_start.container())
1556         return 0;
1557     if (m_start.container()->offsetInCharacters())
1558         return m_start.container();
1559     if (Node* child = m_start.container()->childNode(m_start.offset()))
1560         return child;
1561     if (!m_start.offset())
1562         return m_start.container();
1563     return NodeTraversal::nextSkippingChildren(m_start.container());
1564 }
1565
1566 ShadowRoot* Range::shadowRoot() const
1567 {
1568     return startContainer() ? startContainer()->containingShadowRoot() : 0;
1569 }
1570
1571 Node* Range::pastLastNode() const
1572 {
1573     if (!m_start.container() || !m_end.container())
1574         return 0;
1575     if (m_end.container()->offsetInCharacters())
1576         return NodeTraversal::nextSkippingChildren(m_end.container());
1577     if (Node* child = m_end.container()->childNode(m_end.offset()))
1578         return child;
1579     return NodeTraversal::nextSkippingChildren(m_end.container());
1580 }
1581
1582 IntRect Range::boundingBox() const
1583 {
1584     IntRect result;
1585     Vector<IntRect> rects;
1586     textRects(rects);
1587     const size_t n = rects.size();
1588     for (size_t i = 0; i < n; ++i)
1589         result.unite(rects[i]);
1590     return result;
1591 }
1592
1593 void Range::textRects(Vector<IntRect>& rects, bool useSelectionHeight, RangeInFixedPosition* inFixed) const
1594 {
1595     Node* startContainer = m_start.container();
1596     Node* endContainer = m_end.container();
1597
1598     if (!startContainer || !endContainer) {
1599         if (inFixed)
1600             *inFixed = NotFixedPosition;
1601         return;
1602     }
1603
1604     bool allFixed = true;
1605     bool someFixed = false;
1606
1607     Node* stopNode = pastLastNode();
1608     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
1609         RenderObject* r = node->renderer();
1610         if (!r)
1611             continue;
1612         bool isFixed = false;
1613         if (r->isBR())
1614             r->absoluteRects(rects, flooredLayoutPoint(r->localToAbsolute()));
1615         else if (r->isText()) {
1616             int startOffset = node == startContainer ? m_start.offset() : 0;
1617             int endOffset = node == endContainer ? m_end.offset() : numeric_limits<int>::max();
1618             toRenderText(r)->absoluteRectsForRange(rects, startOffset, endOffset, useSelectionHeight, &isFixed);
1619         } else
1620             continue;
1621         allFixed &= isFixed;
1622         someFixed |= isFixed;
1623     }
1624     
1625     if (inFixed)
1626         *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition);
1627 }
1628
1629 void Range::textQuads(Vector<FloatQuad>& quads, bool useSelectionHeight, RangeInFixedPosition* inFixed) const
1630 {
1631     Node* startContainer = m_start.container();
1632     Node* endContainer = m_end.container();
1633
1634     if (!startContainer || !endContainer) {
1635         if (inFixed)
1636             *inFixed = NotFixedPosition;
1637         return;
1638     }
1639
1640     bool allFixed = true;
1641     bool someFixed = false;
1642
1643     Node* stopNode = pastLastNode();
1644     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
1645         RenderObject* r = node->renderer();
1646         if (!r)
1647             continue;
1648         bool isFixed = false;
1649         if (r->isBR())
1650             r->absoluteQuads(quads, &isFixed);
1651         else if (r->isText()) {
1652             int startOffset = node == startContainer ? m_start.offset() : 0;
1653             int endOffset = node == endContainer ? m_end.offset() : numeric_limits<int>::max();
1654             toRenderText(r)->absoluteQuadsForRange(quads, startOffset, endOffset, useSelectionHeight, &isFixed);
1655         } else
1656             continue;
1657         allFixed &= isFixed;
1658         someFixed |= isFixed;
1659     }
1660
1661     if (inFixed)
1662         *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition);
1663 }
1664
1665 #ifndef NDEBUG
1666 void Range::formatForDebugger(char* buffer, unsigned length) const
1667 {
1668     StringBuilder result;
1669     String s;
1670
1671     if (!m_start.container() || !m_end.container())
1672         result.appendLiteral("<empty>");
1673     else {
1674         const int FormatBufferSize = 1024;
1675         char s[FormatBufferSize];
1676         result.appendLiteral("from offset ");
1677         result.appendNumber(m_start.offset());
1678         result.appendLiteral(" of ");
1679         m_start.container()->formatForDebugger(s, FormatBufferSize);
1680         result.append(s);
1681         result.appendLiteral(" to offset ");
1682         result.appendNumber(m_end.offset());
1683         result.appendLiteral(" of ");
1684         m_end.container()->formatForDebugger(s, FormatBufferSize);
1685         result.append(s);
1686     }
1687
1688     strncpy(buffer, result.toString().utf8().data(), length - 1);
1689 }
1690 #endif
1691
1692 bool areRangesEqual(const Range* a, const Range* b)
1693 {
1694     if (a == b)
1695         return true;
1696     if (!a || !b)
1697         return false;
1698     return a->startPosition() == b->startPosition() && a->endPosition() == b->endPosition();
1699 }
1700
1701 PassRefPtr<Range> rangeOfContents(Node* node)
1702 {
1703     ASSERT(node);
1704     RefPtr<Range> range = Range::create(&node->document());
1705     int exception = 0;
1706     range->selectNodeContents(node, exception);
1707     return range.release();
1708 }
1709
1710 int Range::maxStartOffset() const
1711 {
1712     if (!m_start.container())
1713         return 0;
1714     if (!m_start.container()->offsetInCharacters())
1715         return m_start.container()->childNodeCount();
1716     return m_start.container()->maxCharacterOffset();
1717 }
1718
1719 int Range::maxEndOffset() const
1720 {
1721     if (!m_end.container())
1722         return 0;
1723     if (!m_end.container()->offsetInCharacters())
1724         return m_end.container()->childNodeCount();
1725     return m_end.container()->maxCharacterOffset();
1726 }
1727
1728 static inline void boundaryNodeChildrenChanged(RangeBoundaryPoint& boundary, ContainerNode& container)
1729 {
1730     if (!boundary.childBefore())
1731         return;
1732     if (boundary.container() != &container)
1733         return;
1734     boundary.invalidateOffset();
1735 }
1736
1737 void Range::nodeChildrenChanged(ContainerNode& container)
1738 {
1739     ASSERT(&container.document() == m_ownerDocument);
1740     boundaryNodeChildrenChanged(m_start, container);
1741     boundaryNodeChildrenChanged(m_end, container);
1742 }
1743
1744 static inline void boundaryNodeChildrenWillBeRemoved(RangeBoundaryPoint& boundary, ContainerNode& container)
1745 {
1746     for (Node* nodeToBeRemoved = container.firstChild(); nodeToBeRemoved; nodeToBeRemoved = nodeToBeRemoved->nextSibling()) {
1747         if (boundary.childBefore() == nodeToBeRemoved) {
1748             boundary.setToStartOfNode(&container);
1749             return;
1750         }
1751
1752         for (Node* n = boundary.container(); n; n = n->parentNode()) {
1753             if (n == nodeToBeRemoved) {
1754                 boundary.setToStartOfNode(&container);
1755                 return;
1756             }
1757         }
1758     }
1759 }
1760
1761 void Range::nodeChildrenWillBeRemoved(ContainerNode& container)
1762 {
1763     ASSERT(&container.document() == m_ownerDocument);
1764     boundaryNodeChildrenWillBeRemoved(m_start, container);
1765     boundaryNodeChildrenWillBeRemoved(m_end, container);
1766 }
1767
1768 static inline void boundaryNodeWillBeRemoved(RangeBoundaryPoint& boundary, Node* nodeToBeRemoved)
1769 {
1770     if (boundary.childBefore() == nodeToBeRemoved) {
1771         boundary.childBeforeWillBeRemoved();
1772         return;
1773     }
1774
1775     for (Node* n = boundary.container(); n; n = n->parentNode()) {
1776         if (n == nodeToBeRemoved) {
1777             boundary.setToBeforeChild(nodeToBeRemoved);
1778             return;
1779         }
1780     }
1781 }
1782
1783 void Range::nodeWillBeRemoved(Node* node)
1784 {
1785     ASSERT(node);
1786     ASSERT(&node->document() == m_ownerDocument);
1787     ASSERT(node != m_ownerDocument);
1788     ASSERT(node->parentNode());
1789     boundaryNodeWillBeRemoved(m_start, node);
1790     boundaryNodeWillBeRemoved(m_end, node);
1791 }
1792
1793 static inline void boundaryTextInserted(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
1794 {
1795     if (boundary.container() != text)
1796         return;
1797     unsigned boundaryOffset = boundary.offset();
1798     if (offset >= boundaryOffset)
1799         return;
1800     boundary.setOffset(boundaryOffset + length);
1801 }
1802
1803 void Range::textInserted(Node* text, unsigned offset, unsigned length)
1804 {
1805     ASSERT(text);
1806     ASSERT(&text->document() == m_ownerDocument);
1807     boundaryTextInserted(m_start, text, offset, length);
1808     boundaryTextInserted(m_end, text, offset, length);
1809 }
1810
1811 static inline void boundaryTextRemoved(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
1812 {
1813     if (boundary.container() != text)
1814         return;
1815     unsigned boundaryOffset = boundary.offset();
1816     if (offset >= boundaryOffset)
1817         return;
1818     if (offset + length >= boundaryOffset)
1819         boundary.setOffset(offset);
1820     else
1821         boundary.setOffset(boundaryOffset - length);
1822 }
1823
1824 void Range::textRemoved(Node* text, unsigned offset, unsigned length)
1825 {
1826     ASSERT(text);
1827     ASSERT(&text->document() == m_ownerDocument);
1828     boundaryTextRemoved(m_start, text, offset, length);
1829     boundaryTextRemoved(m_end, text, offset, length);
1830 }
1831
1832 static inline void boundaryTextNodesMerged(RangeBoundaryPoint& boundary, NodeWithIndex& oldNode, unsigned offset)
1833 {
1834     if (boundary.container() == oldNode.node())
1835         boundary.set(oldNode.node()->previousSibling(), boundary.offset() + offset, 0);
1836     else if (boundary.container() == oldNode.node()->parentNode() && boundary.offset() == oldNode.index())
1837         boundary.set(oldNode.node()->previousSibling(), offset, 0);
1838 }
1839
1840 void Range::textNodesMerged(NodeWithIndex& oldNode, unsigned offset)
1841 {
1842     ASSERT(oldNode.node());
1843     ASSERT(&oldNode.node()->document() == m_ownerDocument);
1844     ASSERT(oldNode.node()->parentNode());
1845     ASSERT(oldNode.node()->isTextNode());
1846     ASSERT(oldNode.node()->previousSibling());
1847     ASSERT(oldNode.node()->previousSibling()->isTextNode());
1848     boundaryTextNodesMerged(m_start, oldNode, offset);
1849     boundaryTextNodesMerged(m_end, oldNode, offset);
1850 }
1851
1852 static inline void boundaryTextNodesSplit(RangeBoundaryPoint& boundary, Text* oldNode)
1853 {
1854     if (boundary.container() != oldNode)
1855         return;
1856     unsigned boundaryOffset = boundary.offset();
1857     if (boundaryOffset <= oldNode->length())
1858         return;
1859     boundary.set(oldNode->nextSibling(), boundaryOffset - oldNode->length(), 0);
1860 }
1861
1862 void Range::textNodeSplit(Text* oldNode)
1863 {
1864     ASSERT(oldNode);
1865     ASSERT(&oldNode->document() == m_ownerDocument);
1866     ASSERT(oldNode->parentNode());
1867     ASSERT(oldNode->isTextNode());
1868     ASSERT(oldNode->nextSibling());
1869     ASSERT(oldNode->nextSibling()->isTextNode());
1870     boundaryTextNodesSplit(m_start, oldNode);
1871     boundaryTextNodesSplit(m_end, oldNode);
1872 }
1873
1874 void Range::expand(const String& unit, ExceptionCode& ec)
1875 {
1876     VisiblePosition start(startPosition());
1877     VisiblePosition end(endPosition());
1878     if (unit == "word") {
1879         start = startOfWord(start);
1880         end = endOfWord(end);
1881     } else if (unit == "sentence") {
1882         start = startOfSentence(start);
1883         end = endOfSentence(end);
1884     } else if (unit == "block") {
1885         start = startOfParagraph(start);
1886         end = endOfParagraph(end);
1887     } else if (unit == "document") {
1888         start = startOfDocument(start);
1889         end = endOfDocument(end);
1890     } else
1891         return;
1892     setStart(start.deepEquivalent().containerNode(), start.deepEquivalent().computeOffsetInContainerNode(), ec);
1893     setEnd(end.deepEquivalent().containerNode(), end.deepEquivalent().computeOffsetInContainerNode(), ec);
1894 }
1895
1896 PassRefPtr<ClientRectList> Range::getClientRects() const
1897 {
1898     if (!m_start.container())
1899         return ClientRectList::create();
1900
1901     m_ownerDocument->updateLayoutIgnorePendingStylesheets();
1902
1903     Vector<FloatQuad> quads;
1904     getBorderAndTextQuads(quads);
1905
1906     return ClientRectList::create(quads);
1907 }
1908
1909 PassRefPtr<ClientRect> Range::getBoundingClientRect() const
1910 {
1911     return ClientRect::create(boundingRect());
1912 }
1913
1914 void Range::getBorderAndTextQuads(Vector<FloatQuad>& quads) const
1915 {
1916     Node* startContainer = m_start.container();
1917     Node* endContainer = m_end.container();
1918     Node* stopNode = pastLastNode();
1919
1920     HashSet<Node*> selectedElementsSet;
1921     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
1922         if (node->isElementNode())
1923             selectedElementsSet.add(node);
1924     }
1925
1926     // Don't include elements that are only partially selected.
1927     Node* lastNode = m_end.childBefore() ? m_end.childBefore() : endContainer;
1928     for (Node* parent = lastNode->parentNode(); parent; parent = parent->parentNode())
1929         selectedElementsSet.remove(parent);
1930
1931     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
1932         if (node->isElementNode() && selectedElementsSet.contains(node) && !selectedElementsSet.contains(node->parentNode())) {
1933             if (RenderBoxModelObject* renderBoxModelObject = toElement(node)->renderBoxModelObject()) {
1934                 Vector<FloatQuad> elementQuads;
1935                 renderBoxModelObject->absoluteQuads(elementQuads);
1936                 m_ownerDocument->adjustFloatQuadsForScrollAndAbsoluteZoomAndFrameScale(elementQuads, renderBoxModelObject);
1937
1938                 quads.appendVector(elementQuads);
1939             }
1940         } else if (node->isTextNode()) {
1941             if (RenderObject* renderer = toText(node)->renderer()) {
1942                 RenderText* renderText = toRenderText(renderer);
1943                 int startOffset = (node == startContainer) ? m_start.offset() : 0;
1944                 int endOffset = (node == endContainer) ? m_end.offset() : INT_MAX;
1945                 
1946                 Vector<FloatQuad> textQuads;
1947                 renderText->absoluteQuadsForRange(textQuads, startOffset, endOffset);
1948                 m_ownerDocument->adjustFloatQuadsForScrollAndAbsoluteZoomAndFrameScale(textQuads, renderText);
1949
1950                 quads.appendVector(textQuads);
1951             }
1952         }
1953     }
1954 }
1955
1956 FloatRect Range::boundingRect() const
1957 {
1958     if (!m_start.container())
1959         return FloatRect();
1960
1961     m_ownerDocument->updateLayoutIgnorePendingStylesheets();
1962
1963     Vector<FloatQuad> quads;
1964     getBorderAndTextQuads(quads);
1965     if (quads.isEmpty())
1966         return FloatRect();
1967
1968     FloatRect result;
1969     for (size_t i = 0; i < quads.size(); ++i)
1970         result.unite(quads[i].boundingBox());
1971
1972     return result;
1973 }
1974
1975 } // namespace WebCore
1976
1977 #ifndef NDEBUG
1978
1979 void showTree(const WebCore::Range* range)
1980 {
1981     if (range && range->boundaryPointsValid()) {
1982         range->startContainer()->showTreeAndMark(range->startContainer(), "S", range->endContainer(), "E");
1983         fprintf(stderr, "start offset: %d, end offset: %d\n", range->startOffset(), range->endOffset());
1984     }
1985 }
1986
1987 #endif