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