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