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