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