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