67e52e232e191ad227df97e939e3fa808ef898d6
[WebKit.git] / 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 Apple Inc. All rights reserved.
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Library General Public
10  * License as published by the Free Software Foundation; either
11  * version 2 of the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  * Library General Public License for more details.
17  *
18  * You should have received a copy of the GNU Library General Public License
19  * along with this library; see the file COPYING.LIB.  If not, write to
20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21  * Boston, MA 02110-1301, USA.
22  */
23
24 #include "config.h"
25 #include "Range.h"
26 #include "RangeException.h"
27
28 #include "CString.h"
29 #include "Document.h"
30 #include "DocumentFragment.h"
31 #include "ExceptionCode.h"
32 #include "HTMLElement.h"
33 #include "HTMLNames.h"
34 #include "NodeWithIndex.h"
35 #include "NodeWithIndexAfter.h"
36 #include "NodeWithIndexBefore.h"
37 #include "ProcessingInstruction.h"
38 #include "RenderBlock.h"
39 #include "Text.h"
40 #include "TextIterator.h"
41 #include "markup.h"
42 #include "visible_units.h"
43 #include <stdio.h>
44
45 // FIXME: Remove this after removing Position::offset() and renaming Position::posOffset to offset.
46 #define offset posOffset
47
48 namespace WebCore {
49
50 using namespace std;
51 using namespace HTMLNames;
52
53 #ifndef NDEBUG
54 class RangeCounter {
55 public:
56     static unsigned count;
57     ~RangeCounter()
58     {
59         if (count)
60             fprintf(stderr, "LEAK: %u Range\n", count);
61     }
62 };
63 unsigned RangeCounter::count = 0;
64 static RangeCounter rangeCounter;
65 #endif
66
67 inline Range::Range(PassRefPtr<Document> ownerDocument)
68     : m_ownerDocument(ownerDocument)
69     , m_start(m_ownerDocument, 0)
70     , m_end(m_ownerDocument, 0)
71 {
72 #ifndef NDEBUG
73     ++RangeCounter::count;
74 #endif
75
76     m_ownerDocument->attachRange(this);
77 }
78
79 PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument)
80 {
81     return adoptRef(new Range(ownerDocument));
82 }
83
84 inline Range::Range(PassRefPtr<Document> ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)
85     : m_ownerDocument(ownerDocument)
86     , m_start(m_ownerDocument, 0)
87     , m_end(m_ownerDocument, 0)
88 {
89 #ifndef NDEBUG
90     ++RangeCounter::count;
91 #endif
92
93     m_ownerDocument->attachRange(this);
94
95     // Simply setting the containers and offsets directly would not do any of the checking
96     // that setStart and setEnd do, so we call those functions.
97     ExceptionCode ec = 0;
98     setStart(startContainer, startOffset, ec);
99     ASSERT(!ec);
100     setEnd(endContainer, endOffset, ec);
101     ASSERT(!ec);
102 }
103
104 PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)
105 {
106     return adoptRef(new Range(ownerDocument, startContainer, startOffset, endContainer, endOffset));
107 }
108
109 PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument, const Position& start, const Position& end)
110 {
111     return adoptRef(new Range(ownerDocument, start.container.get(), start.offset, end.container.get(), end.offset));
112 }
113
114 Range::~Range()
115 {
116     if (m_start.container)
117         m_ownerDocument->detachRange(this);
118
119 #ifndef NDEBUG
120     --RangeCounter::count;
121 #endif
122 }
123
124 Node* Range::startContainer(ExceptionCode& ec) const
125 {
126     if (!m_start.container) {
127         ec = INVALID_STATE_ERR;
128         return 0;
129     }
130
131     return m_start.container.get();
132 }
133
134 int Range::startOffset(ExceptionCode& ec) const
135 {
136     if (!m_start.container) {
137         ec = INVALID_STATE_ERR;
138         return 0;
139     }
140
141     return m_start.offset;
142 }
143
144 Node* Range::endContainer(ExceptionCode& ec) const
145 {
146     if (!m_start.container) {
147         ec = INVALID_STATE_ERR;
148         return 0;
149     }
150
151     return m_end.container.get();
152 }
153
154 int Range::endOffset(ExceptionCode& ec) const
155 {
156     if (!m_start.container) {
157         ec = INVALID_STATE_ERR;
158         return 0;
159     }
160
161     return m_end.offset;
162 }
163
164 Node* Range::commonAncestorContainer(ExceptionCode& ec) const
165 {
166     if (!m_start.container) {
167         ec = INVALID_STATE_ERR;
168         return 0;
169     }
170
171     return commonAncestorContainer(m_start.container.get(), m_end.container.get());
172 }
173
174 Node* Range::commonAncestorContainer(Node* containerA, Node* containerB)
175 {
176     for (Node* parentA = containerA; parentA; parentA = parentA->parentNode()) {
177         for (Node* parentB = containerB; parentB; parentB = parentB->parentNode()) {
178             if (parentA == parentB)
179                 return parentA;
180         }
181     }
182     return 0;
183 }
184
185 bool Range::collapsed(ExceptionCode& ec) const
186 {
187     if (!m_start.container) {
188         ec = INVALID_STATE_ERR;
189         return 0;
190     }
191
192     return m_start.container == m_end.container && m_start.offset == m_end.offset;
193 }
194
195 void Range::setStart(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
196 {
197     if (!m_start.container) {
198         ec = INVALID_STATE_ERR;
199         return;
200     }
201
202     if (!refNode) {
203         ec = NOT_FOUND_ERR;
204         return;
205     }
206
207     if (refNode->document() != m_ownerDocument) {
208         ec = WRONG_DOCUMENT_ERR;
209         return;
210     }
211
212     ec = 0;
213     checkNodeWOffset(refNode.get(), offset, ec);
214     if (ec)
215         return;
216
217     m_start.container = refNode;
218     m_start.offset = offset;
219
220     // check if different root container
221     Node* endRootContainer = m_end.container.get();
222     while (endRootContainer->parentNode())
223         endRootContainer = endRootContainer->parentNode();
224     Node* startRootContainer = m_start.container.get();
225     while (startRootContainer->parentNode())
226         startRootContainer = startRootContainer->parentNode();
227     if (startRootContainer != endRootContainer)
228         collapse(true, ec);
229     // check if new start after end
230     else if (compareBoundaryPoints(m_start.container.get(), m_start.offset, m_end.container.get(), m_end.offset) > 0)
231         collapse(true, ec);
232 }
233
234 void Range::setEnd(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
235 {
236     if (!m_start.container) {
237         ec = INVALID_STATE_ERR;
238         return;
239     }
240
241     if (!refNode) {
242         ec = NOT_FOUND_ERR;
243         return;
244     }
245
246     if (refNode->document() != m_ownerDocument) {
247         ec = WRONG_DOCUMENT_ERR;
248         return;
249     }
250
251     ec = 0;
252     checkNodeWOffset(refNode.get(), offset, ec);
253     if (ec)
254         return;
255
256     m_end.container = refNode;
257     m_end.offset = offset;
258
259     // check if different root container
260     Node* endRootContainer = m_end.container.get();
261     while (endRootContainer->parentNode())
262         endRootContainer = endRootContainer->parentNode();
263     Node* startRootContainer = m_start.container.get();
264     while (startRootContainer->parentNode())
265         startRootContainer = startRootContainer->parentNode();
266     if (startRootContainer != endRootContainer)
267         collapse(false, ec);
268     // check if new end before start
269     if (compareBoundaryPoints(m_start.container.get(), m_start.offset, m_end.container.get(), m_end.offset) > 0)
270         collapse(false, ec);
271 }
272
273 void Range::collapse(bool toStart, ExceptionCode& ec)
274 {
275     if (!m_start.container) {
276         ec = INVALID_STATE_ERR;
277         return;
278     }
279
280     if (toStart)
281         m_end = m_start;
282     else
283         m_start = m_end;
284 }
285
286 bool Range::isPointInRange(Node* refNode, int offset, ExceptionCode& ec)
287 {
288     if (!refNode) {
289         ec = NOT_FOUND_ERR;
290         return false;
291     }
292
293     if (!m_start.container && refNode->attached()) {
294         ec = INVALID_STATE_ERR;
295         return false;
296     }
297
298     if (m_start.container && !refNode->attached()) {
299         // Firefox doesn't throw an exception for this case; it returns false.
300         return false;
301     }
302
303     if (refNode->document() != m_ownerDocument) {
304         ec = WRONG_DOCUMENT_ERR;
305         return false;
306     }
307
308     ec = 0;
309     checkNodeWOffset(refNode, offset, ec);
310     if (ec)
311         return false;
312
313     return compareBoundaryPoints(refNode, offset, m_start.container.get(), m_start.offset) >= 0
314         && compareBoundaryPoints(refNode, offset, m_end.container.get(), m_end.offset) <= 0;
315 }
316
317 short Range::comparePoint(Node* refNode, int offset, ExceptionCode& ec)
318 {
319     // http://developer.mozilla.org/en/docs/DOM:range.comparePoint
320     // This method returns -1, 0 or 1 depending on if the point described by the 
321     // refNode node and an offset within the node is before, same as, or after the range respectively.
322
323     if (!refNode) {
324         ec = NOT_FOUND_ERR;
325         return 0;
326     }
327
328     if (!m_start.container && refNode->attached()) {
329         ec = INVALID_STATE_ERR;
330         return 0;
331     }
332
333     if (m_start.container && !refNode->attached()) {
334         // Firefox doesn't throw an exception for this case; it returns -1.
335         return -1;
336     }
337
338     if (refNode->document() != m_ownerDocument) {
339         ec = WRONG_DOCUMENT_ERR;
340         return 0;
341     }
342
343     ec = 0;
344     checkNodeWOffset(refNode, offset, ec);
345     if (ec)
346         return 0;
347
348     // compare to start, and point comes before
349     if (compareBoundaryPoints(refNode, offset, m_start.container.get(), m_start.offset) < 0)
350         return -1;
351
352     // compare to end, and point comes after
353     if (compareBoundaryPoints(refNode, offset, m_end.container.get(), m_end.offset) > 0)
354         return 1;
355
356     // point is in the middle of this range, or on the boundary points
357     return 0;
358 }
359
360 Range::CompareResults Range::compareNode(Node* refNode, ExceptionCode& ec)
361 {
362     // http://developer.mozilla.org/en/docs/DOM:range.compareNode
363     // This method returns 0, 1, 2, or 3 based on if the node is before, after,
364     // before and after(surrounds), or inside the range, respectively
365
366     if (!refNode) {
367         ec = NOT_FOUND_ERR;
368         return NODE_BEFORE;
369     }
370     
371     if (!m_start.container && refNode->attached()) {
372         ec = INVALID_STATE_ERR;
373         return NODE_BEFORE;
374     }
375
376     if (m_start.container && !refNode->attached()) {
377         // Firefox doesn't throw an exception for this case; it returns 0.
378         return NODE_BEFORE;
379     }
380
381     if (refNode->document() != m_ownerDocument) {
382         // Firefox doesn't throw an exception for this case; it returns 0.
383         return NODE_BEFORE;
384     }
385
386     Node* parentNode = refNode->parentNode();
387     int nodeIndex = refNode->nodeIndex();
388     
389     if (!parentNode) {
390         // if the node is the top document we should return NODE_BEFORE_AND_AFTER
391         // but we throw to match firefox behavior
392         ec = NOT_FOUND_ERR;
393         return NODE_BEFORE;
394     }
395
396     if (comparePoint(parentNode, nodeIndex, ec) < 0) { // starts before
397         if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range
398             return NODE_BEFORE_AND_AFTER;
399         return NODE_BEFORE; // ends before or in the range
400     } else { // starts at or after the range start
401         if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range
402             return NODE_AFTER;
403         return NODE_INSIDE; // ends inside the range
404     }
405 }
406
407
408 short Range::compareBoundaryPoints(CompareHow how, const Range* sourceRange, ExceptionCode& ec) const
409 {
410     if (!m_start.container) {
411         ec = INVALID_STATE_ERR;
412         return 0;
413     }
414
415     if (!sourceRange) {
416         ec = NOT_FOUND_ERR;
417         return 0;
418     }
419
420     ec = 0;
421     Node* thisCont = commonAncestorContainer(ec);
422     if (ec)
423         return 0;
424     Node* sourceCont = sourceRange->commonAncestorContainer(ec);
425     if (ec)
426         return 0;
427
428     if (thisCont->document() != sourceCont->document()) {
429         ec = WRONG_DOCUMENT_ERR;
430         return 0;
431     }
432
433     Node* thisTop = thisCont;
434     Node* sourceTop = sourceCont;
435     while (thisTop->parentNode())
436         thisTop = thisTop->parentNode();
437     while (sourceTop->parentNode())
438         sourceTop = sourceTop->parentNode();
439     if (thisTop != sourceTop) { // in different DocumentFragments
440         ec = WRONG_DOCUMENT_ERR;
441         return 0;
442     }
443
444     switch (how) {
445         case START_TO_START:
446             return compareBoundaryPoints(m_start.container.get(), m_start.offset,
447                 sourceRange->m_start.container.get(), sourceRange->m_start.offset);
448         case START_TO_END:
449             return compareBoundaryPoints(m_start.container.get(), m_start.offset,
450                 sourceRange->m_end.container.get(), sourceRange->m_end.offset);
451         case END_TO_END:
452             return compareBoundaryPoints(m_end.container.get(), m_end.offset,
453                 sourceRange->m_end.container.get(), sourceRange->m_end.offset);
454         case END_TO_START:
455             return compareBoundaryPoints(m_end.container.get(), m_end.offset,
456                 sourceRange->m_start.container.get(), sourceRange->m_start.offset);
457     }
458
459     ec = SYNTAX_ERR;
460     return 0;
461 }
462
463 short Range::compareBoundaryPoints(Node* containerA, int offsetA, Node* containerB, int offsetB)
464 {
465     ASSERT(containerA && containerB);
466     if (!containerA)
467         return -1;
468     if (!containerB)
469         return 1;
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         return 0;
523     Node* childA = containerA;
524     while (childA && childA->parentNode() != commonAncestor)
525         childA = childA->parentNode();
526     if (!childA)
527         childA = commonAncestor;
528     Node* childB = containerB;
529     while (childB && childB->parentNode() != commonAncestor)
530         childB = childB->parentNode();
531     if (!childB)
532         childB = commonAncestor;
533
534     if (childA == childB)
535         return 0; // A is equal to B
536
537     Node* n = commonAncestor->firstChild();
538     while (n) {
539         if (n == childA)
540             return -1; // A is before B
541         if (n == childB)
542             return 1; // A is after B
543         n = n->nextSibling();
544     }
545
546     // Should never reach this point.
547     ASSERT_NOT_REACHED();
548     return 0;
549 }
550
551 short Range::compareBoundaryPoints(const Position& a, const Position& b)
552 {
553     return compareBoundaryPoints(a.container.get(), a.offset, b.container.get(), b.offset);
554 }
555
556 bool Range::boundaryPointsValid() const
557 {
558     return m_start.container && compareBoundaryPoints(m_start.container.get(), m_start.offset, m_end.container.get(), m_end.offset) <= 0;
559 }
560
561 void Range::deleteContents(ExceptionCode& ec)
562 {
563     checkDeleteExtract(ec);
564     if (ec)
565         return;
566
567     processContents(DELETE_CONTENTS, ec);
568 }
569
570 bool Range::intersectsNode(Node* refNode, ExceptionCode& ec)
571 {
572     // http://developer.mozilla.org/en/docs/DOM:range.intersectsNode
573     // Returns a bool if the node intersects the range.
574
575     if (!refNode) {
576         ec = NOT_FOUND_ERR;
577         return false;
578     }
579     
580     if (!m_start.container && refNode->attached()
581             || m_start.container && !refNode->attached()
582             || refNode->document() != m_ownerDocument) {
583         // Firefox doesn't throw an exception for these cases; it returns false.
584         return false;
585     }
586
587     Node* parentNode = refNode->parentNode();
588     int nodeIndex = refNode->nodeIndex();
589     
590     if (!parentNode) {
591         // if the node is the top document we should return NODE_BEFORE_AND_AFTER
592         // but we throw to match firefox behavior
593         ec = NOT_FOUND_ERR;
594         return false;
595     }
596
597     if (comparePoint(parentNode, nodeIndex, ec) < 0 && // starts before start
598         comparePoint(parentNode, nodeIndex + 1, ec) < 0) { // ends before start
599         return false;
600     } else if (comparePoint(parentNode, nodeIndex, ec) > 0 && // starts after end
601                comparePoint(parentNode, nodeIndex + 1, ec) > 0) { // ends after end
602         return false;
603     }
604     
605     return true; // all other cases
606 }
607
608 PassRefPtr<DocumentFragment> Range::processContents(ActionType action, ExceptionCode& ec)
609 {
610     // FIXME: To work properly with mutation events, we will have to take into account
611     // situations where the tree is being transformed while we work on it - ugh!
612
613     RefPtr<DocumentFragment> fragment;
614     if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)
615         fragment = new DocumentFragment(m_ownerDocument.get());
616     
617     ec = 0;
618     if (collapsed(ec))
619         return fragment.release();
620     if (ec)
621         return 0;
622
623     Node* commonRoot = commonAncestorContainer(ec);
624     if (ec)
625         return 0;
626     ASSERT(commonRoot);
627
628     // what is the highest node that partially selects the start of the range?
629     Node* partialStart = 0;
630     if (m_start.container != commonRoot) {
631         partialStart = m_start.container.get();
632         while (partialStart->parentNode() != commonRoot)
633             partialStart = partialStart->parentNode();
634     }
635
636     // what is the highest node that partially selects the end of the range?
637     Node* partialEnd = 0;
638     if (m_end.container != commonRoot) {
639         partialEnd = m_end.container.get();
640         while (partialEnd->parentNode() != commonRoot)
641             partialEnd = partialEnd->parentNode();
642     }
643
644     // Simple case: the start and end containers are the same. We just grab
645     // everything >= start offset and < end offset
646     if (m_start.container == m_end.container) {
647         Node::NodeType startNodeType = m_start.container->nodeType();
648         if (startNodeType == Node::TEXT_NODE || startNodeType == Node::CDATA_SECTION_NODE || startNodeType == Node::COMMENT_NODE) {
649             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
650                 RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(m_start.container->cloneNode(true));
651                 c->deleteData(m_end.offset, c->length() - m_end.offset, ec);
652                 c->deleteData(0, m_start.offset, ec);
653                 fragment->appendChild(c.release(), ec);
654             }
655             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS)
656                 static_cast<CharacterData*>(m_start.container.get())->deleteData(m_start.offset, m_end.offset - m_start.offset, ec);
657         } else if (startNodeType == Node::PROCESSING_INSTRUCTION_NODE) {
658             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
659                 RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(m_start.container->cloneNode(true));
660                 c->setData(c->data().substring(m_start.offset, m_end.offset - m_start.offset), ec);
661                 fragment->appendChild(c.release(), ec);
662             }
663             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
664                 ProcessingInstruction* pi = static_cast<ProcessingInstruction*>(m_start.container.get());
665                 String data(pi->data());
666                 data.remove(m_start.offset, m_end.offset - m_start.offset);
667                 pi->setData(data, ec);
668             }
669         } else {
670             Node* n = m_start.container->firstChild();
671             int i;
672             for (i = 0; n && i < m_start.offset; i++) // skip until start offset
673                 n = n->nextSibling();
674             int endOffset = m_end.offset;
675             while (n && i < endOffset) { // delete until end offset
676                 Node* next = n->nextSibling();
677                 if (action == EXTRACT_CONTENTS)
678                     fragment->appendChild(n, ec); // will remove n from its parent
679                 else if (action == CLONE_CONTENTS)
680                     fragment->appendChild(n->cloneNode(true), ec);
681                 else
682                     m_start.container->removeChild(n, ec);
683                 n = next;
684                 i++;
685             }
686         }
687         return fragment.release();
688     }
689
690     // Complex case: Start and end containers are different.
691     // There are three possiblities here:
692     // 1. Start container == commonRoot (End container must be a descendant)
693     // 2. End container == commonRoot (Start container must be a descendant)
694     // 3. Neither is commonRoot, they are both descendants
695     //
696     // In case 3, we grab everything after the start (up until a direct child
697     // of commonRoot) into leftContents, and everything before the end (up until
698     // a direct child of commonRoot) into rightContents. Then we process all
699     // commonRoot children between leftContents and rightContents
700     //
701     // In case 1 or 2, we skip either processing of leftContents or rightContents,
702     // in which case the last lot of nodes either goes from the first or last
703     // child of commonRoot.
704     //
705     // These are deleted, cloned, or extracted (i.e. both) depending on action.
706
707     RefPtr<Node> leftContents;
708     if (m_start.container != commonRoot) {
709         // process the left-hand side of the range, up until the last ancestor of
710         // start container before commonRoot
711         Node::NodeType startNodeType = m_start.container->nodeType();
712         if (startNodeType == Node::TEXT_NODE || startNodeType == Node::CDATA_SECTION_NODE || startNodeType == Node::COMMENT_NODE) {
713             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
714                 RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(m_start.container->cloneNode(true));
715                 c->deleteData(0, m_start.offset, ec);
716                 leftContents = c.release();
717             }
718             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS)
719                 static_cast<CharacterData*>(m_start.container.get())->deleteData(
720                     m_start.offset, static_cast<CharacterData*>(m_start.container.get())->length() - m_start.offset, ec);
721         } else if (startNodeType == Node::PROCESSING_INSTRUCTION_NODE) {
722             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
723                 RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(m_start.container->cloneNode(true));
724                 c->setData(c->data().substring(m_start.offset), ec);
725                 leftContents = c.release();
726             }
727             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
728                 ProcessingInstruction* pi = static_cast<ProcessingInstruction*>(m_start.container.get());
729                 String data(pi->data());
730                 pi->setData(data.left(m_start.offset), ec);
731             }
732         } else {
733             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)
734                 leftContents = m_start.container->cloneNode(false);
735             Node* n = m_start.container->firstChild();
736             for (int i = 0; n && i < m_start.offset; i++) // skip until start offset
737                 n = n->nextSibling();
738             while (n) { // process until end
739                 Node* next = n->nextSibling();
740                 if (action == EXTRACT_CONTENTS)
741                     leftContents->appendChild(n, ec); // will remove n from start container
742                 else if (action == CLONE_CONTENTS)
743                     leftContents->appendChild(n->cloneNode(true), ec);
744                 else
745                     m_start.container->removeChild(n, ec);
746                 n = next;
747             }
748         }
749
750         Node* leftParent = m_start.container->parentNode();
751         Node* n = m_start.container->nextSibling();
752         for (; leftParent != commonRoot; leftParent = leftParent->parentNode()) {
753             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
754                 RefPtr<Node> leftContentsParent = leftParent->cloneNode(false);
755                 leftContentsParent->appendChild(leftContents,ec);
756                 leftContents = leftContentsParent;
757             }
758
759             Node* next;
760             for (; n; n = next) {
761                 next = n->nextSibling();
762                 if (action == EXTRACT_CONTENTS)
763                     leftContents->appendChild(n,ec); // will remove n from leftParent
764                 else if (action == CLONE_CONTENTS)
765                     leftContents->appendChild(n->cloneNode(true),ec);
766                 else
767                     leftParent->removeChild(n,ec);
768             }
769             n = leftParent->nextSibling();
770         }
771     }
772
773     RefPtr<Node> rightContents;
774     if (m_end.container != commonRoot) {
775         // delete the right-hand side of the range, up until the last ancestor of
776         // end container before commonRoot
777         Node::NodeType endNodeType = m_end.container->nodeType();
778         if (endNodeType == Node::TEXT_NODE || endNodeType == Node::CDATA_SECTION_NODE || endNodeType == Node::COMMENT_NODE) {
779             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
780                 RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(m_end.container->cloneNode(true));
781                 c->deleteData(m_end.offset, static_cast<CharacterData*>(m_end.container.get())->length() - m_end.offset, ec);
782                 rightContents = c;
783             }
784             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS)
785                 static_cast<CharacterData*>(m_end.container.get())->deleteData(0, m_end.offset, ec);
786         } else if (endNodeType == Node::PROCESSING_INSTRUCTION_NODE) {
787             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
788                 RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(m_end.container->cloneNode(true));
789                 c->setData(c->data().left(m_end.offset), ec);
790                 rightContents = c.release();
791             }
792             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
793                 ProcessingInstruction* pi = static_cast<ProcessingInstruction*>(m_end.container.get());
794                 pi->setData(pi->data().substring(m_end.offset), ec);
795             }
796         } else {
797             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)
798                 rightContents = m_end.container->cloneNode(false);
799             Node* n = m_end.container->firstChild();
800             if (n && m_end.offset) {
801                 for (int i = 0; i + 1 < m_end.offset; i++) { // skip to end.offset
802                     Node* next = n->nextSibling();
803                     if (!next)
804                         break;
805                     n = next;
806                 }
807                 Node* prev;
808                 for (; n; n = prev) {
809                     prev = n->previousSibling();
810                     if (action == EXTRACT_CONTENTS)
811                         rightContents->insertBefore(n, rightContents->firstChild(), ec); // will remove n from its parent
812                     else if (action == CLONE_CONTENTS)
813                         rightContents->insertBefore(n->cloneNode(true), rightContents->firstChild(), ec);
814                     else
815                         m_end.container->removeChild(n, ec);
816                 }
817             }
818         }
819
820         Node* rightParent = m_end.container->parentNode();
821         Node* n = m_end.container->previousSibling();
822         for (; rightParent != commonRoot; rightParent = rightParent->parentNode()) {
823             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
824                 RefPtr<Node> rightContentsParent = rightParent->cloneNode(false);
825                 rightContentsParent->appendChild(rightContents,ec);
826                 rightContents = rightContentsParent;
827             }
828             Node* prev;
829             for (; n; n = prev) {
830                 prev = n->previousSibling();
831                 if (action == EXTRACT_CONTENTS)
832                     rightContents->insertBefore(n, rightContents->firstChild(), ec); // will remove n from its parent
833                 else if (action == CLONE_CONTENTS)
834                     rightContents->insertBefore(n->cloneNode(true), rightContents->firstChild(), ec);
835                 else
836                     rightParent->removeChild(n, ec);
837             }
838             n = rightParent->previousSibling();
839         }
840     }
841
842     // delete all children of commonRoot between the start and end container
843
844     Node* processStart; // child of commonRoot
845     if (m_start.container == commonRoot) {
846         processStart = m_start.container->firstChild();
847         for (int i = 0; i < m_start.offset; i++)
848             processStart = processStart->nextSibling();
849     } else {
850         processStart = m_start.container.get();
851         while (processStart->parentNode() != commonRoot)
852             processStart = processStart->parentNode();
853         processStart = processStart->nextSibling();
854     }
855     Node* processEnd; // child of commonRoot
856     if (m_end.container == commonRoot) {
857         processEnd = m_end.container->firstChild();
858         for (int i = 0; i < m_end.offset; i++)
859             processEnd = processEnd->nextSibling();
860     } else {
861         processEnd = m_end.container.get();
862         while (processEnd->parentNode() != commonRoot)
863             processEnd = processEnd->parentNode();
864     }
865
866     // Now add leftContents, stuff in between, and rightContents to the fragment
867     // (or just delete the stuff in between)
868
869     if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && leftContents)
870         fragment->appendChild(leftContents, ec);
871
872     Node* next;
873     Node* n;
874     if (processStart) {
875         for (n = processStart; n && n != processEnd; n = next) {
876             next = n->nextSibling();
877             if (action == EXTRACT_CONTENTS)
878                 fragment->appendChild(n, ec); // will remove from commonRoot
879             else if (action == CLONE_CONTENTS)
880                 fragment->appendChild(n->cloneNode(true), ec);
881             else
882                 commonRoot->removeChild(n, ec);
883         }
884     }
885
886     if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && rightContents)
887         fragment->appendChild(rightContents, ec);
888
889     return fragment.release();
890 }
891
892 PassRefPtr<DocumentFragment> Range::extractContents(ExceptionCode& ec)
893 {
894     checkDeleteExtract(ec);
895     if (ec)
896         return 0;
897
898     return processContents(EXTRACT_CONTENTS, ec);
899 }
900
901 PassRefPtr<DocumentFragment> Range::cloneContents(ExceptionCode& ec)
902 {
903     if (!m_start.container) {
904         ec = INVALID_STATE_ERR;
905         return 0;
906     }
907
908     return processContents(CLONE_CONTENTS, ec);
909 }
910
911 void Range::insertNode(PassRefPtr<Node> newNode, ExceptionCode& ec)
912 {
913     ec = 0;
914
915     if (!m_start.container) {
916         ec = INVALID_STATE_ERR;
917         return;
918     }
919
920     if (!newNode) {
921         ec = NOT_FOUND_ERR;
922         return;
923     }
924
925     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
926     // the Range is read-only.
927     if (containedByReadOnly()) {
928         ec = NO_MODIFICATION_ALLOWED_ERR;
929         return;
930     }
931
932     // WRONG_DOCUMENT_ERR: Raised if newParent and the container of the start of the Range were
933     // not created from the same document.
934     if (newNode->document() != m_start.container->document()) {
935         ec = WRONG_DOCUMENT_ERR;
936         return;
937     }
938
939     // HIERARCHY_REQUEST_ERR: Raised if the container of the start of the Range is of a type that
940     // does not allow children of the type of newNode or if newNode is an ancestor of the container.
941
942     // an extra one here - if a text node is going to split, it must have a parent to insert into
943     if (m_start.container->nodeType() == Node::TEXT_NODE && !m_start.container->parentNode()) {
944         ec = HIERARCHY_REQUEST_ERR;
945         return;
946     }
947
948     // In the case where the container is a text node, we check against the container's parent, because
949     // text nodes get split up upon insertion.
950     Node* checkAgainst;
951     if (m_start.container->nodeType() == Node::TEXT_NODE)
952         checkAgainst = m_start.container->parentNode();
953     else
954         checkAgainst = m_start.container.get();
955
956     if (newNode->nodeType() == Node::DOCUMENT_FRAGMENT_NODE) {
957         // check each child node, not the DocumentFragment itself
958         for (Node* c = newNode->firstChild(); c; c = c->nextSibling()) {
959             if (!checkAgainst->childTypeAllowed(c->nodeType())) {
960                 ec = HIERARCHY_REQUEST_ERR;
961                 return;
962             }
963         }
964     } else {
965         if (!checkAgainst->childTypeAllowed(newNode->nodeType())) {
966             ec = HIERARCHY_REQUEST_ERR;
967             return;
968         }
969     }
970
971     for (Node* n = m_start.container.get(); n; n = n->parentNode()) {
972         if (n == newNode) {
973             ec = HIERARCHY_REQUEST_ERR;
974             return;
975         }
976     }
977
978     // INVALID_NODE_TYPE_ERR: Raised if newNode is an Attr, Entity, Notation, or Document node.
979     if (newNode->nodeType() == Node::ATTRIBUTE_NODE ||
980         newNode->nodeType() == Node::ENTITY_NODE ||
981         newNode->nodeType() == Node::NOTATION_NODE ||
982         newNode->nodeType() == Node::DOCUMENT_NODE) {
983         ec = RangeException::INVALID_NODE_TYPE_ERR;
984         return;
985     }
986
987     int endOffsetDelta = 0;
988     if (m_start.container->nodeType() == Node::TEXT_NODE ||
989         m_start.container->nodeType() == Node::CDATA_SECTION_NODE) {
990         RefPtr<Text> newText = static_cast<Text*>(m_start.container.get())->splitText(m_start.offset, ec);
991         if (ec)
992             return;
993         if (m_start.container == m_end.container)
994             endOffsetDelta = -m_start.offset;
995         m_start.container->parentNode()->insertBefore(newNode, newText.get(), ec);
996         if (ec)
997             return;
998         m_end.container = newText;
999     } else {
1000         if (m_start.container == m_end.container) {
1001             bool isFragment = newNode->nodeType() == Node::DOCUMENT_FRAGMENT_NODE;
1002             endOffsetDelta = isFragment ? newNode->childNodeCount() : 1;
1003         }
1004
1005         m_start.container->insertBefore(newNode, m_start.container->childNode(m_start.offset), ec);
1006         if (ec)
1007             return;
1008     }
1009     m_end.offset += endOffsetDelta;
1010 }
1011
1012 String Range::toString(ExceptionCode& ec) const
1013 {
1014     if (!m_start.container) {
1015         ec = INVALID_STATE_ERR;
1016         return String();
1017     }
1018
1019     Vector<UChar> result;
1020
1021     Node* pastLast = pastLastNode();
1022     for (Node* n = firstNode(); n != pastLast; n = n->traverseNextNode()) {
1023         if (n->nodeType() == Node::TEXT_NODE || n->nodeType() == Node::CDATA_SECTION_NODE) {
1024             String data = static_cast<CharacterData*>(n)->data();
1025             int length = data.length();
1026             int start = (n == m_start.container) ? min(max(0, m_start.offset), length) : 0;
1027             int end = (n == m_end.container) ? min(max(start, m_end.offset), length) : length;
1028             result.append(data.characters() + start, end - start);
1029         }
1030     }
1031
1032     return String::adopt(result);
1033 }
1034
1035 String Range::toHTML() const
1036 {
1037     return createMarkup(this);
1038 }
1039
1040 String Range::text() const
1041 {
1042     if (!m_start.container)
1043         return String();
1044
1045     // We need to update layout, since plainText uses line boxes in the render tree.
1046     // FIXME: As with innerText, we'd like this to work even if there are no render objects.
1047     m_start.container->document()->updateLayout();
1048
1049     return plainText(this);
1050 }
1051
1052 PassRefPtr<DocumentFragment> Range::createContextualFragment(const String& markup, ExceptionCode& ec) const
1053 {
1054     if (!m_start.container) {
1055         ec = INVALID_STATE_ERR;
1056         return 0;
1057     }
1058
1059     Node* element = m_start.container->isElementNode() ? m_start.container.get() : m_start.container->parentNode();
1060     if (!element || !element->isHTMLElement()) {
1061         ec = NOT_SUPPORTED_ERR;
1062         return 0;
1063     }
1064
1065     RefPtr<DocumentFragment> fragment = static_cast<HTMLElement*>(element)->createContextualFragment(markup);
1066     if (!fragment) {
1067         ec = NOT_SUPPORTED_ERR;
1068         return 0;
1069     }
1070
1071     return fragment.release();
1072 }
1073
1074
1075 void Range::detach(ExceptionCode& ec)
1076 {
1077     if (!m_start.container) {
1078         ec = INVALID_STATE_ERR;
1079         return;
1080     }
1081
1082     m_ownerDocument->detachRange(this);
1083
1084     m_start.clear();
1085     m_end.clear();
1086 }
1087
1088 void Range::checkNodeWOffset(Node* n, int offset, ExceptionCode& ec) const
1089 {
1090     switch (n->nodeType()) {
1091         case Node::DOCUMENT_TYPE_NODE:
1092         case Node::ENTITY_NODE:
1093         case Node::NOTATION_NODE:
1094             ec = RangeException::INVALID_NODE_TYPE_ERR;
1095             return;
1096         case Node::CDATA_SECTION_NODE:
1097         case Node::COMMENT_NODE:
1098         case Node::TEXT_NODE:
1099             if (static_cast<unsigned>(offset) > static_cast<CharacterData*>(n)->length())
1100                 ec = INDEX_SIZE_ERR;
1101             return;
1102         case Node::PROCESSING_INSTRUCTION_NODE:
1103             if (static_cast<unsigned>(offset) > static_cast<ProcessingInstruction*>(n)->data().length())
1104                 ec = INDEX_SIZE_ERR;
1105             return;
1106         case Node::ATTRIBUTE_NODE:
1107         case Node::DOCUMENT_FRAGMENT_NODE:
1108         case Node::DOCUMENT_NODE:
1109         case Node::ELEMENT_NODE:
1110         case Node::ENTITY_REFERENCE_NODE:
1111         case Node::XPATH_NAMESPACE_NODE:
1112             if (static_cast<unsigned>(offset) > n->childNodeCount())
1113                 ec = INDEX_SIZE_ERR;
1114             return;
1115     }
1116     ASSERT_NOT_REACHED();
1117 }
1118
1119 void Range::checkNodeBA(Node* n, ExceptionCode& ec) const
1120 {
1121     // INVALID_NODE_TYPE_ERR: Raised if the root container of refNode is not an
1122     // Attr, Document or DocumentFragment node or part of a shadow DOM tree
1123     // or if refNode is a Document, DocumentFragment, Attr, Entity, or Notation node.
1124
1125     switch (n->nodeType()) {
1126         case Node::ATTRIBUTE_NODE:
1127         case Node::DOCUMENT_FRAGMENT_NODE:
1128         case Node::DOCUMENT_NODE:
1129         case Node::ENTITY_NODE:
1130         case Node::NOTATION_NODE:
1131             ec = RangeException::INVALID_NODE_TYPE_ERR;
1132             return;
1133         case Node::CDATA_SECTION_NODE:
1134         case Node::COMMENT_NODE:
1135         case Node::DOCUMENT_TYPE_NODE:
1136         case Node::ELEMENT_NODE:
1137         case Node::ENTITY_REFERENCE_NODE:
1138         case Node::PROCESSING_INSTRUCTION_NODE:
1139         case Node::TEXT_NODE:
1140         case Node::XPATH_NAMESPACE_NODE:
1141             break;
1142     }
1143
1144     Node* root = n;
1145     while (Node* parent = root->parentNode())
1146         root = parent;
1147
1148     switch (root->nodeType()) {
1149         case Node::ATTRIBUTE_NODE:
1150         case Node::DOCUMENT_NODE:
1151         case Node::DOCUMENT_FRAGMENT_NODE:
1152             break;
1153         case Node::CDATA_SECTION_NODE:
1154         case Node::COMMENT_NODE:
1155         case Node::DOCUMENT_TYPE_NODE:
1156         case Node::ELEMENT_NODE:
1157         case Node::ENTITY_NODE:
1158         case Node::ENTITY_REFERENCE_NODE:
1159         case Node::NOTATION_NODE:
1160         case Node::PROCESSING_INSTRUCTION_NODE:
1161         case Node::TEXT_NODE:
1162         case Node::XPATH_NAMESPACE_NODE:
1163             if (root->isShadowNode())
1164                 break;
1165             ec = RangeException::INVALID_NODE_TYPE_ERR;
1166             return;
1167     }
1168 }
1169
1170 PassRefPtr<Range> Range::cloneRange(ExceptionCode& ec) const
1171 {
1172     if (!m_start.container) {
1173         ec = INVALID_STATE_ERR;
1174         return 0;
1175     }
1176
1177     return Range::create(m_ownerDocument, m_start.container, m_start.offset, m_end.container, m_end.offset);
1178 }
1179
1180 void Range::setStartAfter(Node* refNode, ExceptionCode& ec)
1181 {
1182     if (!m_start.container) {
1183         ec = INVALID_STATE_ERR;
1184         return;
1185     }
1186
1187     if (!refNode) {
1188         ec = NOT_FOUND_ERR;
1189         return;
1190     }
1191
1192     if (refNode->document() != m_ownerDocument) {
1193         ec = WRONG_DOCUMENT_ERR;
1194         return;
1195     }
1196
1197     ec = 0;
1198     checkNodeBA(refNode, ec);
1199     if (ec)
1200         return;
1201
1202     setStart(refNode->parentNode(), refNode->nodeIndex() + 1, ec);
1203 }
1204
1205 void Range::setEndBefore(Node* refNode, ExceptionCode& ec)
1206 {
1207     if (!m_start.container) {
1208         ec = INVALID_STATE_ERR;
1209         return;
1210     }
1211
1212     if (!refNode) {
1213         ec = NOT_FOUND_ERR;
1214         return;
1215     }
1216
1217     if (refNode->document() != m_ownerDocument) {
1218         ec = WRONG_DOCUMENT_ERR;
1219         return;
1220     }
1221
1222     ec = 0;
1223     checkNodeBA(refNode, ec);
1224     if (ec)
1225         return;
1226
1227     setEnd(refNode->parentNode(), refNode->nodeIndex(), ec);
1228 }
1229
1230 void Range::setEndAfter(Node* refNode, ExceptionCode& ec)
1231 {
1232     if (!m_start.container) {
1233         ec = INVALID_STATE_ERR;
1234         return;
1235     }
1236
1237     if (!refNode) {
1238         ec = NOT_FOUND_ERR;
1239         return;
1240     }
1241
1242     if (refNode->document() != m_ownerDocument) {
1243         ec = WRONG_DOCUMENT_ERR;
1244         return;
1245     }
1246
1247     ec = 0;
1248     checkNodeBA(refNode, ec);
1249     if (ec)
1250         return;
1251
1252     setEnd(refNode->parentNode(), refNode->nodeIndex() + 1, ec);
1253
1254 }
1255
1256 void Range::selectNode(Node* refNode, ExceptionCode& ec)
1257 {
1258     if (!m_start.container) {
1259         ec = INVALID_STATE_ERR;
1260         return;
1261     }
1262
1263     if (!refNode) {
1264         ec = NOT_FOUND_ERR;
1265         return;
1266     }
1267
1268     // INVALID_NODE_TYPE_ERR: Raised if an ancestor of refNode is an Entity, Notation or
1269     // DocumentType node or if refNode is a Document, DocumentFragment, Attr, Entity, or Notation
1270     // node.
1271     for (Node* anc = refNode->parentNode(); anc; anc = anc->parentNode()) {
1272         switch (anc->nodeType()) {
1273             case Node::ATTRIBUTE_NODE:
1274             case Node::CDATA_SECTION_NODE:
1275             case Node::COMMENT_NODE:
1276             case Node::DOCUMENT_FRAGMENT_NODE:
1277             case Node::DOCUMENT_NODE:
1278             case Node::ELEMENT_NODE:
1279             case Node::ENTITY_REFERENCE_NODE:
1280             case Node::PROCESSING_INSTRUCTION_NODE:
1281             case Node::TEXT_NODE:
1282             case Node::XPATH_NAMESPACE_NODE:
1283                 break;
1284             case Node::DOCUMENT_TYPE_NODE:
1285             case Node::ENTITY_NODE:
1286             case Node::NOTATION_NODE:
1287                 ec = RangeException::INVALID_NODE_TYPE_ERR;
1288                 return;
1289         }
1290     }
1291
1292     switch (refNode->nodeType()) {
1293         case Node::CDATA_SECTION_NODE:
1294         case Node::COMMENT_NODE:
1295         case Node::DOCUMENT_TYPE_NODE:
1296         case Node::ELEMENT_NODE:
1297         case Node::ENTITY_REFERENCE_NODE:
1298         case Node::PROCESSING_INSTRUCTION_NODE:
1299         case Node::TEXT_NODE:
1300         case Node::XPATH_NAMESPACE_NODE:
1301             break;
1302         case Node::ATTRIBUTE_NODE:
1303         case Node::DOCUMENT_FRAGMENT_NODE:
1304         case Node::DOCUMENT_NODE:
1305         case Node::ENTITY_NODE:
1306         case Node::NOTATION_NODE:
1307             ec = RangeException::INVALID_NODE_TYPE_ERR;
1308             return;
1309     }
1310
1311     ec = 0;
1312     setStartBefore(refNode, ec);
1313     if (ec)
1314         return;
1315     setEndAfter(refNode, ec);
1316 }
1317
1318 void Range::selectNodeContents(Node* refNode, ExceptionCode& ec)
1319 {
1320     if (!m_start.container) {
1321         ec = INVALID_STATE_ERR;
1322         return;
1323     }
1324
1325     if (!refNode) {
1326         ec = NOT_FOUND_ERR;
1327         return;
1328     }
1329
1330     // INVALID_NODE_TYPE_ERR: Raised if refNode or an ancestor of refNode is an Entity, Notation
1331     // or DocumentType node.
1332     for (Node* n = refNode; n; n = n->parentNode()) {
1333         switch (n->nodeType()) {
1334             case Node::ATTRIBUTE_NODE:
1335             case Node::CDATA_SECTION_NODE:
1336             case Node::COMMENT_NODE:
1337             case Node::DOCUMENT_FRAGMENT_NODE:
1338             case Node::DOCUMENT_NODE:
1339             case Node::ELEMENT_NODE:
1340             case Node::ENTITY_REFERENCE_NODE:
1341             case Node::PROCESSING_INSTRUCTION_NODE:
1342             case Node::TEXT_NODE:
1343             case Node::XPATH_NAMESPACE_NODE:
1344                 break;
1345             case Node::DOCUMENT_TYPE_NODE:
1346             case Node::ENTITY_NODE:
1347             case Node::NOTATION_NODE:
1348                 ec = RangeException::INVALID_NODE_TYPE_ERR;
1349                 return;
1350         }
1351     }
1352
1353     m_start.container = refNode;
1354     m_start.offset = 0;
1355     m_end.container = refNode;
1356     m_end.offset = maxEndOffset();
1357 }
1358
1359 void Range::surroundContents(PassRefPtr<Node> passNewParent, ExceptionCode& ec)
1360 {
1361     RefPtr<Node> newParent = passNewParent;
1362
1363     if (!m_start.container) {
1364         ec = INVALID_STATE_ERR;
1365         return;
1366     }
1367
1368     if (!newParent) {
1369         ec = NOT_FOUND_ERR;
1370         return;
1371     }
1372
1373     // INVALID_NODE_TYPE_ERR: Raised if node is an Attr, Entity, DocumentType, Notation,
1374     // Document, or DocumentFragment node.
1375     switch (newParent->nodeType()) {
1376         case Node::ATTRIBUTE_NODE:
1377         case Node::DOCUMENT_FRAGMENT_NODE:
1378         case Node::DOCUMENT_NODE:
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         case Node::CDATA_SECTION_NODE:
1385         case Node::COMMENT_NODE:
1386         case Node::ELEMENT_NODE:
1387         case Node::ENTITY_REFERENCE_NODE:
1388         case Node::PROCESSING_INSTRUCTION_NODE:
1389         case Node::TEXT_NODE:
1390         case Node::XPATH_NAMESPACE_NODE:
1391             break;
1392     }
1393
1394     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
1395     // the Range is read-only.
1396     if (containedByReadOnly()) {
1397         ec = NO_MODIFICATION_ALLOWED_ERR;
1398         return;
1399     }
1400
1401     // WRONG_DOCUMENT_ERR: Raised if newParent and the container of the start of the Range were
1402     // not created from the same document.
1403     if (newParent->document() != m_start.container->document()) {
1404         ec = WRONG_DOCUMENT_ERR;
1405         return;
1406     }
1407
1408     // Raise a HIERARCHY_REQUEST_ERR if m_start.container doesn't accept children like newParent.
1409     Node* parentOfNewParent = m_start.container.get();
1410
1411     // If m_start.container is a character data node, it will be split and it will be its parent that will 
1412     // need to accept newParent (or in the case of a comment, it logically "would"
1413     if (parentOfNewParent->isCharacterDataNode())
1414         parentOfNewParent = parentOfNewParent->parentNode();
1415     if (!parentOfNewParent->childTypeAllowed(newParent->nodeType())) {
1416         ec = HIERARCHY_REQUEST_ERR;
1417         return;
1418     }
1419     
1420     if (m_start.container == newParent || m_start.container->isDescendantOf(newParent.get())) {
1421         ec = HIERARCHY_REQUEST_ERR;
1422         return;
1423     }
1424
1425     // FIXME: Do we need a check if the node would end up with a child node of a type not
1426     // allowed by the type of node?
1427
1428     // BAD_BOUNDARYPOINTS_ERR: Raised if the Range partially selects a non-Text node.
1429     if (m_start.container->nodeType() != Node::TEXT_NODE) {
1430         if (m_start.offset > 0 && m_start.offset < maxStartOffset()) {
1431             ec = RangeException::BAD_BOUNDARYPOINTS_ERR;
1432             return;
1433         }
1434     }
1435     if (m_end.container->nodeType() != Node::TEXT_NODE) {
1436         if (m_end.offset > 0 && m_end.offset < maxEndOffset()) {
1437             ec = RangeException::BAD_BOUNDARYPOINTS_ERR;
1438             return;
1439         }
1440     }    
1441
1442     ec = 0;
1443     while (Node* n = newParent->firstChild()) {
1444         newParent->removeChild(n, ec);
1445         if (ec)
1446             return;
1447     }
1448     RefPtr<DocumentFragment> fragment = extractContents(ec);
1449     if (ec)
1450         return;
1451     insertNode(newParent, ec);
1452     if (ec)
1453         return;
1454     newParent->appendChild(fragment.release(), ec);
1455     if (ec)
1456         return;
1457     selectNode(newParent.get(), ec);
1458 }
1459
1460 void Range::setStartBefore(Node* refNode, ExceptionCode& ec)
1461 {
1462     if (!m_start.container) {
1463         ec = INVALID_STATE_ERR;
1464         return;
1465     }
1466
1467     if (!refNode) {
1468         ec = NOT_FOUND_ERR;
1469         return;
1470     }
1471
1472     if (refNode->document() != m_ownerDocument) {
1473         ec = WRONG_DOCUMENT_ERR;
1474         return;
1475     }
1476
1477     ec = 0;
1478     checkNodeBA(refNode, ec);
1479     if (ec)
1480         return;
1481
1482     setStart(refNode->parentNode(), refNode->nodeIndex(), ec);
1483 }
1484
1485 void Range::checkDeleteExtract(ExceptionCode& ec)
1486 {
1487     if (!m_start.container) {
1488         ec = INVALID_STATE_ERR;
1489         return;
1490     }
1491
1492     ec = 0;
1493     if (!commonAncestorContainer(ec) || ec)
1494         return;
1495         
1496     Node* pastLast = pastLastNode();
1497     for (Node* n = firstNode(); n != pastLast; n = n->traverseNextNode()) {
1498         if (n->isReadOnlyNode()) {
1499             ec = NO_MODIFICATION_ALLOWED_ERR;
1500             return;
1501         }
1502         if (n->nodeType() == Node::DOCUMENT_TYPE_NODE) { // ### is this for only directly under the DF, or anywhere?
1503             ec = HIERARCHY_REQUEST_ERR;
1504             return;
1505         }
1506     }
1507
1508     if (containedByReadOnly()) {
1509         ec = NO_MODIFICATION_ALLOWED_ERR;
1510         return;
1511     }
1512 }
1513
1514 bool Range::containedByReadOnly() const
1515 {
1516     for (Node* n = m_start.container.get(); n; n = n->parentNode()) {
1517         if (n->isReadOnlyNode())
1518             return true;
1519     }
1520     for (Node* n = m_end.container.get(); n; n = n->parentNode()) {
1521         if (n->isReadOnlyNode())
1522             return true;
1523     }
1524     return false;
1525 }
1526
1527 Node* Range::firstNode() const
1528 {
1529     if (!m_start.container)
1530         return 0;
1531     if (m_start.container->offsetInCharacters())
1532         return m_start.container.get();
1533     if (Node* child = m_start.container->childNode(m_start.offset))
1534         return child;
1535     if (!m_start.offset)
1536         return m_start.container.get();
1537     return m_start.container->traverseNextSibling();
1538 }
1539
1540 Position Range::editingStartPosition() const
1541 {
1542     // This function is used by range style computations to avoid bugs like:
1543     // <rdar://problem/4017641> REGRESSION (Mail): you can only bold/unbold a selection starting from end of line once
1544     // It is important to skip certain irrelevant content at the start of the selection, so we do not wind up 
1545     // with a spurious "mixed" style.
1546     
1547     VisiblePosition visiblePosition(m_start.container.get(), m_start.offset, VP_DEFAULT_AFFINITY);
1548     if (visiblePosition.isNull())
1549         return Position();
1550
1551     ExceptionCode ec = 0;
1552     // if the selection is a caret, just return the position, since the style
1553     // behind us is relevant
1554     if (collapsed(ec))
1555         return visiblePosition.deepEquivalent();
1556
1557     // if the selection starts just before a paragraph break, skip over it
1558     if (isEndOfParagraph(visiblePosition))
1559         return visiblePosition.next().deepEquivalent().downstream();
1560
1561     // otherwise, make sure to be at the start of the first selected node,
1562     // instead of possibly at the end of the last node before the selection
1563     return visiblePosition.deepEquivalent().downstream();
1564 }
1565
1566 Node* Range::pastLastNode() const
1567 {
1568     if (!m_start.container || !m_end.container)
1569         return 0;
1570     if (m_end.container->offsetInCharacters())
1571         return m_end.container->traverseNextSibling();
1572     if (Node* child = m_end.container->childNode(m_end.offset))
1573         return child;
1574     return m_end.container->traverseNextSibling();
1575 }
1576
1577 IntRect Range::boundingBox()
1578 {
1579     IntRect result;
1580     Vector<IntRect> rects;
1581     addLineBoxRects(rects);
1582     const size_t n = rects.size();
1583     for (size_t i = 0; i < n; ++i)
1584         result.unite(rects[i]);
1585     return result;
1586 }
1587
1588 void Range::addLineBoxRects(Vector<IntRect>& rects, bool useSelectionHeight)
1589 {
1590     if (!m_start.container || !m_end.container)
1591         return;
1592
1593     RenderObject* start = m_start.container->renderer();
1594     RenderObject* end = m_end.container->renderer();
1595     if (!start || !end)
1596         return;
1597
1598     RenderObject* stop = end->nextInPreOrderAfterChildren();
1599     for (RenderObject* r = start; r && r != stop; r = r->nextInPreOrder()) {
1600         // only ask leaf render objects for their line box rects
1601         if (!r->firstChild()) {
1602             int startOffset = r == start ? m_start.offset : 0;
1603             int endOffset = r == end ? m_end.offset : UINT_MAX;
1604             r->addLineBoxRects(rects, startOffset, endOffset, useSelectionHeight);
1605         }
1606     }
1607 }
1608
1609 #ifndef NDEBUG
1610 #define FormatBufferSize 1024
1611 void Range::formatForDebugger(char* buffer, unsigned length) const
1612 {
1613     String result;
1614     String s;
1615     
1616     if (!m_start.container || !m_end.container)
1617         result = "<empty>";
1618     else {
1619         char s[FormatBufferSize];
1620         result += "from offset ";
1621         result += String::number(m_start.offset);
1622         result += " of ";
1623         m_start.container->formatForDebugger(s, FormatBufferSize);
1624         result += s;
1625         result += " to offset ";
1626         result += String::number(m_end.offset);
1627         result += " of ";
1628         m_end.container->formatForDebugger(s, FormatBufferSize);
1629         result += s;
1630     }
1631           
1632     strncpy(buffer, result.utf8().data(), length - 1);
1633 }
1634 #undef FormatBufferSize
1635 #endif
1636
1637 bool operator==(const Range& a, const Range& b)
1638 {
1639     if (&a == &b)
1640         return true;
1641     // Not strictly legal C++, but in practice this can happen, and this check works
1642     // fine with GCC to detect such cases and return false rather than crashing.
1643     if (!&a || !&b)
1644         return false;
1645     return a.startPosition() == b.startPosition() && a.endPosition() == b.endPosition();
1646 }
1647
1648 PassRefPtr<Range> rangeOfContents(Node* node)
1649 {
1650     ASSERT(node);
1651     RefPtr<Range> range = Range::create(node->document());
1652     int exception = 0;
1653     range->selectNodeContents(node, exception);
1654     return range.release();
1655 }
1656
1657 int Range::maxStartOffset() const
1658 {
1659     if (!m_start.container)
1660         return 0;
1661     if (!m_start.container->offsetInCharacters())
1662         return m_start.container->childNodeCount();
1663     return m_start.container->maxCharacterOffset();
1664 }
1665
1666 int Range::maxEndOffset() const
1667 {
1668     if (!m_end.container)
1669         return 0;
1670     if (!m_end.container->offsetInCharacters())
1671         return m_end.container->childNodeCount();
1672     return m_end.container->maxCharacterOffset();
1673 }
1674
1675 static inline void endpointNodeChildrenChanged(Position& endpoint,
1676     NodeWithIndexAfter& beforeChange, NodeWithIndexBefore& afterChange, int childCountDelta)
1677 {
1678     if (endpoint.container != afterChange.parent())
1679         return;
1680     if (beforeChange.indexAfter() >= endpoint.offset)
1681         return;
1682     if (childCountDelta < 0 && afterChange.indexBefore() >= endpoint.offset)
1683         endpoint.offset = afterChange.indexBefore();
1684     else
1685         endpoint.offset += childCountDelta;
1686 }
1687
1688 void Range::nodeChildrenChanged(NodeWithIndexAfter& beforeChange, NodeWithIndexBefore& afterChange, int childCountDelta)
1689 {
1690     ASSERT(afterChange.parent());
1691     ASSERT(afterChange.parent()->document() == m_ownerDocument);
1692     ASSERT(childCountDelta);
1693     endpointNodeChildrenChanged(m_start, beforeChange, afterChange, childCountDelta);
1694     endpointNodeChildrenChanged(m_end, beforeChange, afterChange, childCountDelta);
1695 }
1696
1697 static inline void endpointNodeWillBeRemoved(Position& endpoint, NodeWithIndex& nodeToBeRemoved)
1698 {
1699     for (Node* n = endpoint.container.get(); n; n = n->parentNode()) {
1700         if (n == nodeToBeRemoved.node()) {
1701             endpoint.container = nodeToBeRemoved.node()->parentNode();
1702             endpoint.offset = nodeToBeRemoved.index();
1703         }
1704     }
1705 }
1706
1707 void Range::nodeWillBeRemoved(NodeWithIndex& nodeToBeRemoved)
1708 {
1709     ASSERT(nodeToBeRemoved.node());
1710     ASSERT(nodeToBeRemoved.node()->document() == m_ownerDocument);
1711     ASSERT(nodeToBeRemoved.node() != m_ownerDocument);
1712     ASSERT(nodeToBeRemoved.node()->parentNode());
1713     endpointNodeWillBeRemoved(m_start, nodeToBeRemoved);
1714     endpointNodeWillBeRemoved(m_end, nodeToBeRemoved);
1715 }
1716
1717 static inline void endpointTextInserted(Position& endpoint, Node* text, unsigned offset, unsigned length)
1718 {
1719     if (endpoint.container != text)
1720         return;
1721     if (offset >= static_cast<unsigned>(endpoint.offset))
1722         return;
1723     endpoint.offset += length;
1724 }
1725
1726 void Range::textInserted(Node* text, unsigned offset, unsigned length)
1727 {
1728     ASSERT(text);
1729     ASSERT(text->document() == m_ownerDocument);
1730     endpointTextInserted(m_start, text, offset, length);
1731     endpointTextInserted(m_end, text, offset, length);
1732 }
1733
1734 static inline void endpointTextRemoved(Position& endpoint, Node* text, unsigned offset, unsigned length)
1735 {
1736     if (endpoint.container != text)
1737         return;
1738     if (offset >= static_cast<unsigned>(endpoint.offset))
1739         return;
1740     if (offset + length >= static_cast<unsigned>(endpoint.offset))
1741         endpoint.offset = offset;
1742     else
1743         endpoint.offset -= length;
1744 }
1745
1746 void Range::textRemoved(Node* text, unsigned offset, unsigned length)
1747 {
1748     ASSERT(text);
1749     ASSERT(text->document() == m_ownerDocument);
1750     endpointTextRemoved(m_start, text, offset, length);
1751     endpointTextRemoved(m_end, text, offset, length);
1752 }
1753
1754 static inline void endpointTextNodesMerged(Position& endpoint, NodeWithIndex& oldNode, unsigned offset)
1755 {
1756     if (endpoint.container == oldNode.node()) {
1757         endpoint.container = oldNode.node()->previousSibling();
1758         endpoint.offset += offset;
1759     } else if (endpoint.container == oldNode.node()->parentNode() && endpoint.offset == oldNode.index()) {
1760         endpoint.container = oldNode.node()->previousSibling();
1761         endpoint.offset = offset;
1762     }
1763 }
1764
1765 void Range::textNodesMerged(NodeWithIndex& oldNode, unsigned offset)
1766 {
1767     ASSERT(oldNode.node());
1768     ASSERT(oldNode.node()->document() == m_ownerDocument);
1769     ASSERT(oldNode.node()->parentNode());
1770     ASSERT(oldNode.node()->isTextNode());
1771     ASSERT(oldNode.node()->previousSibling());
1772     ASSERT(oldNode.node()->previousSibling()->isTextNode());
1773     endpointTextNodesMerged(m_start, oldNode, offset);
1774     endpointTextNodesMerged(m_end, oldNode, offset);
1775 }
1776
1777 static inline void endpointTextNodesSplit(Position& endpoint, Text* oldNode)
1778 {
1779     if (endpoint.container != oldNode)
1780         return;
1781     if (endpoint.offset <= static_cast<int>(oldNode->length()))
1782         return;
1783     endpoint.container = oldNode->nextSibling();
1784     endpoint.offset -= oldNode->length();
1785 }
1786
1787 void Range::textNodeSplit(Text* oldNode)
1788 {
1789     ASSERT(oldNode);
1790     ASSERT(oldNode->document() == m_ownerDocument);
1791     ASSERT(oldNode->parentNode());
1792     ASSERT(oldNode->isTextNode());
1793     ASSERT(oldNode->nextSibling());
1794     ASSERT(oldNode->nextSibling()->isTextNode());
1795     endpointTextNodesSplit(m_start, oldNode);
1796     endpointTextNodesSplit(m_end, oldNode);
1797 }
1798
1799 }