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