Streamline use of TextIterator, cutting down includes and use of soon-to-be-deleted...
[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  * Copyright (C) 2011 Motorola Mobility. All rights reserved.
8  *
9  * This library is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU Library General Public
11  * License as published by the Free Software Foundation; either
12  * version 2 of the License, or (at your option) any later version.
13  *
14  * This library is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17  * Library General Public License for more details.
18  *
19  * You should have received a copy of the GNU Library General Public License
20  * along with this library; see the file COPYING.LIB.  If not, write to
21  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
22  * Boston, MA 02110-1301, USA.
23  */
24
25 #include "config.h"
26 #include "Range.h"
27
28 #include "ClientRect.h"
29 #include "ClientRectList.h"
30 #include "DocumentFragment.h"
31 #include "Frame.h"
32 #include "FrameView.h"
33 #include "HTMLElement.h"
34 #include "HTMLNames.h"
35 #include "NodeTraversal.h"
36 #include "NodeWithIndex.h"
37 #include "Page.h"
38 #include "ProcessingInstruction.h"
39 #include "RangeException.h"
40 #include "RenderBoxModelObject.h"
41 #include "RenderText.h"
42 #include "ScopedEventQueue.h"
43 #include "TextIterator.h"
44 #include "VisiblePosition.h"
45 #include "VisibleUnits.h"
46 #include "htmlediting.h"
47 #include "markup.h"
48 #include <stdio.h>
49 #include <wtf/RefCountedLeakCounter.h>
50 #include <wtf/text/CString.h>
51 #include <wtf/text/StringBuilder.h>
52
53 #if PLATFORM(IOS)
54 #include "SelectionRect.h"
55 #endif
56
57 namespace WebCore {
58
59 using namespace HTMLNames;
60
61 DEFINE_DEBUG_ONLY_GLOBAL(WTF::RefCountedLeakCounter, rangeCounter, ("Range"));
62
63 inline Range::Range(Document& ownerDocument)
64     : m_ownerDocument(ownerDocument)
65     , m_start(&ownerDocument)
66     , m_end(&ownerDocument)
67 {
68 #ifndef NDEBUG
69     rangeCounter.increment();
70 #endif
71
72     m_ownerDocument->attachRange(this);
73 }
74
75 PassRefPtr<Range> Range::create(Document& ownerDocument)
76 {
77     return adoptRef(new Range(ownerDocument));
78 }
79
80 inline Range::Range(Document& ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)
81     : m_ownerDocument(ownerDocument)
82     , m_start(&ownerDocument)
83     , m_end(&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(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(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 PassRefPtr<Range> Range::create(ScriptExecutionContext& context)
108 {
109     return adoptRef(new Range(toDocument(context)));
110 }
111
112 #if PLATFORM(IOS)
113 PassRefPtr<Range> Range::create(Document& ownerDocument, const VisiblePosition& visibleStart, const VisiblePosition& visibleEnd)
114 {
115     Position start = visibleStart.deepEquivalent().parentAnchoredEquivalent();
116     Position end = visibleEnd.deepEquivalent().parentAnchoredEquivalent();
117     return adoptRef(new Range(ownerDocument, start.anchorNode(), start.deprecatedEditingOffset(), end.anchorNode(), end.deprecatedEditingOffset()));
118 }
119 #endif
120
121 Range::~Range()
122 {
123     // Always detach (even if we've already detached) to fix https://bugs.webkit.org/show_bug.cgi?id=26044
124     m_ownerDocument->detachRange(this);
125
126 #ifndef NDEBUG
127     rangeCounter.decrement();
128 #endif
129 }
130
131 void Range::setDocument(Document& document)
132 {
133     ASSERT(&m_ownerDocument.get() != &document);
134     m_ownerDocument->detachRange(this);
135     m_ownerDocument = document;
136     m_start.setToStartOfNode(&document);
137     m_end.setToStartOfNode(&document);
138     m_ownerDocument->attachRange(this);
139 }
140
141 Node* Range::startContainer(ExceptionCode& ec) const
142 {
143     if (!m_start.container()) {
144         ec = INVALID_STATE_ERR;
145         return 0;
146     }
147
148     return m_start.container();
149 }
150
151 int Range::startOffset(ExceptionCode& ec) const
152 {
153     if (!m_start.container()) {
154         ec = INVALID_STATE_ERR;
155         return 0;
156     }
157
158     return m_start.offset();
159 }
160
161 Node* Range::endContainer(ExceptionCode& ec) const
162 {
163     if (!m_start.container()) {
164         ec = INVALID_STATE_ERR;
165         return 0;
166     }
167
168     return m_end.container();
169 }
170
171 int Range::endOffset(ExceptionCode& ec) const
172 {
173     if (!m_start.container()) {
174         ec = INVALID_STATE_ERR;
175         return 0;
176     }
177
178     return m_end.offset();
179 }
180
181 Node* Range::commonAncestorContainer(ExceptionCode& ec) const
182 {
183     if (!m_start.container()) {
184         ec = INVALID_STATE_ERR;
185         return 0;
186     }
187
188     return commonAncestorContainer(m_start.container(), m_end.container());
189 }
190
191 Node* Range::commonAncestorContainer(Node* containerA, Node* containerB)
192 {
193     for (Node* parentA = containerA; parentA; parentA = parentA->parentNode()) {
194         for (Node* parentB = containerB; parentB; parentB = parentB->parentNode()) {
195             if (parentA == parentB)
196                 return parentA;
197         }
198     }
199     return 0;
200 }
201
202 bool Range::collapsed(ExceptionCode& ec) const
203 {
204     if (!m_start.container()) {
205         ec = INVALID_STATE_ERR;
206         return 0;
207     }
208
209     return m_start == m_end;
210 }
211
212 static inline bool checkForDifferentRootContainer(const RangeBoundaryPoint& start, const RangeBoundaryPoint& end)
213 {
214     Node* endRootContainer = end.container();
215     while (endRootContainer->parentNode())
216         endRootContainer = endRootContainer->parentNode();
217     Node* startRootContainer = start.container();
218     while (startRootContainer->parentNode())
219         startRootContainer = startRootContainer->parentNode();
220
221     return startRootContainer != endRootContainer || (Range::compareBoundaryPoints(start, end, ASSERT_NO_EXCEPTION) > 0);
222 }
223
224 void Range::setStart(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
225 {
226     if (!m_start.container()) {
227         ec = INVALID_STATE_ERR;
228         return;
229     }
230
231     if (!refNode) {
232         ec = NOT_FOUND_ERR;
233         return;
234     }
235
236     bool didMoveDocument = false;
237     if (&refNode->document() != &ownerDocument()) {
238         setDocument(refNode->document());
239         didMoveDocument = true;
240     }
241
242     ec = 0;
243     Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);
244     if (ec)
245         return;
246
247     m_start.set(refNode, offset, childNode);
248
249     if (didMoveDocument || checkForDifferentRootContainer(m_start, m_end))
250         collapse(true, ec);
251 }
252
253 void Range::setEnd(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
254 {
255     if (!m_start.container()) {
256         ec = INVALID_STATE_ERR;
257         return;
258     }
259
260     if (!refNode) {
261         ec = NOT_FOUND_ERR;
262         return;
263     }
264
265     bool didMoveDocument = false;
266     if (&refNode->document() != &ownerDocument()) {
267         setDocument(refNode->document());
268         didMoveDocument = true;
269     }
270
271     ec = 0;
272     Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);
273     if (ec)
274         return;
275
276     m_end.set(refNode, offset, childNode);
277
278     if (didMoveDocument || checkForDifferentRootContainer(m_start, m_end))
279         collapse(false, ec);
280 }
281
282 void Range::setStart(const Position& start, ExceptionCode& ec)
283 {
284     Position parentAnchored = start.parentAnchoredEquivalent();
285     setStart(parentAnchored.containerNode(), parentAnchored.offsetInContainerNode(), ec);
286 }
287
288 void Range::setEnd(const Position& end, ExceptionCode& ec)
289 {
290     Position parentAnchored = end.parentAnchoredEquivalent();
291     setEnd(parentAnchored.containerNode(), parentAnchored.offsetInContainerNode(), ec);
292 }
293
294 void Range::collapse(bool toStart, ExceptionCode& ec)
295 {
296     if (!m_start.container()) {
297         ec = INVALID_STATE_ERR;
298         return;
299     }
300
301     if (toStart)
302         m_end = m_start;
303     else
304         m_start = m_end;
305 }
306
307 bool Range::isPointInRange(Node* refNode, int offset, ExceptionCode& ec)
308 {
309     if (!m_start.container()) {
310         ec = INVALID_STATE_ERR;
311         return false;
312     }
313
314     if (!refNode) {
315         ec = HIERARCHY_REQUEST_ERR;
316         return false;
317     }
318
319     if (!refNode->inDocument() || &refNode->document() != &ownerDocument()) {
320         return false;
321     }
322
323     ec = 0;
324     checkNodeWOffset(refNode, offset, ec);
325     if (ec)
326         return false;
327
328     return compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset(), ec) >= 0 && !ec
329         && compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset(), ec) <= 0 && !ec;
330 }
331
332 short Range::comparePoint(Node* refNode, int offset, ExceptionCode& ec) const
333 {
334     // http://developer.mozilla.org/en/docs/DOM:range.comparePoint
335     // This method returns -1, 0 or 1 depending on if the point described by the 
336     // refNode node and an offset within the node is before, same as, or after the range respectively.
337
338     if (!m_start.container()) {
339         ec = INVALID_STATE_ERR;
340         return 0;
341     }
342
343     if (!refNode) {
344         ec = HIERARCHY_REQUEST_ERR;
345         return 0;
346     }
347
348     if (!refNode->inDocument() || &refNode->document() != &ownerDocument()) {
349         ec = WRONG_DOCUMENT_ERR;
350         return 0;
351     }
352
353     ec = 0;
354     checkNodeWOffset(refNode, offset, ec);
355     if (ec)
356         return 0;
357
358     // compare to start, and point comes before
359     if (compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset(), ec) < 0)
360         return -1;
361
362     if (ec)
363         return 0;
364
365     // compare to end, and point comes after
366     if (compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset(), ec) > 0 && !ec)
367         return 1;
368
369     // point is in the middle of this range, or on the boundary points
370     return 0;
371 }
372
373 Range::CompareResults Range::compareNode(Node* refNode, ExceptionCode& ec) const
374 {
375     // http://developer.mozilla.org/en/docs/DOM:range.compareNode
376     // This method returns 0, 1, 2, or 3 based on if the node is before, after,
377     // before and after(surrounds), or inside the range, respectively
378
379     if (!refNode) {
380         ec = NOT_FOUND_ERR;
381         return NODE_BEFORE;
382     }
383     
384     if (!m_start.container() && refNode->inDocument()) {
385         ec = INVALID_STATE_ERR;
386         return NODE_BEFORE;
387     }
388
389     if (m_start.container() && !refNode->inDocument()) {
390         // Firefox doesn't throw an exception for this case; it returns 0.
391         return NODE_BEFORE;
392     }
393
394     if (&refNode->document() != &ownerDocument()) {
395         // Firefox doesn't throw an exception for this case; it returns 0.
396         return NODE_BEFORE;
397     }
398
399     ContainerNode* parentNode = refNode->parentNode();
400     int nodeIndex = refNode->nodeIndex();
401     
402     if (!parentNode) {
403         // if the node is the top document we should return NODE_BEFORE_AND_AFTER
404         // but we throw to match firefox behavior
405         ec = NOT_FOUND_ERR;
406         return NODE_BEFORE;
407     }
408
409     if (comparePoint(parentNode, nodeIndex, ec) < 0) { // starts before
410         if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range
411             return NODE_BEFORE_AND_AFTER;
412         return NODE_BEFORE; // ends before or in the range
413     } else { // starts at or after the range start
414         if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range
415             return NODE_AFTER;
416         return NODE_INSIDE; // ends inside the range
417     }
418 }
419
420 short Range::compareBoundaryPoints(CompareHow how, const Range* sourceRange, ExceptionCode& ec) const
421 {
422     if (!m_start.container()) {
423         ec = INVALID_STATE_ERR;
424         return 0;
425     }
426
427     if (!sourceRange) {
428         ec = NOT_FOUND_ERR;
429         return 0;
430     }
431
432     ec = 0;
433     Node* thisCont = commonAncestorContainer(ec);
434     if (ec)
435         return 0;
436     Node* sourceCont = sourceRange->commonAncestorContainer(ec);
437     if (ec)
438         return 0;
439
440     if (&thisCont->document() != &sourceCont->document()) {
441         ec = WRONG_DOCUMENT_ERR;
442         return 0;
443     }
444
445     Node* thisTop = thisCont;
446     Node* sourceTop = sourceCont;
447     while (thisTop->parentNode())
448         thisTop = thisTop->parentNode();
449     while (sourceTop->parentNode())
450         sourceTop = sourceTop->parentNode();
451     if (thisTop != sourceTop) { // in different DocumentFragments
452         ec = WRONG_DOCUMENT_ERR;
453         return 0;
454     }
455
456     switch (how) {
457         case START_TO_START:
458             return compareBoundaryPoints(m_start, sourceRange->m_start, ec);
459         case START_TO_END:
460             return compareBoundaryPoints(m_end, sourceRange->m_start, ec);
461         case END_TO_END:
462             return compareBoundaryPoints(m_end, sourceRange->m_end, ec);
463         case END_TO_START:
464             return compareBoundaryPoints(m_start, sourceRange->m_end, ec);
465     }
466
467     ec = SYNTAX_ERR;
468     return 0;
469 }
470
471 short Range::compareBoundaryPoints(Node* containerA, int offsetA, Node* containerB, int offsetB, ExceptionCode& ec)
472 {
473     ASSERT(containerA);
474     ASSERT(containerB);
475
476     if (!containerA)
477         return -1;
478     if (!containerB)
479         return 1;
480
481     // see DOM2 traversal & range section 2.5
482
483     // case 1: both points have the same container
484     if (containerA == containerB) {
485         if (offsetA == offsetB)
486             return 0;           // A is equal to B
487         if (offsetA < offsetB)
488             return -1;          // A is before B
489         else
490             return 1;           // A is after B
491     }
492
493     // case 2: node C (container B or an ancestor) is a child node of A
494     Node* c = containerB;
495     while (c && c->parentNode() != containerA)
496         c = c->parentNode();
497     if (c) {
498         int offsetC = 0;
499         Node* n = containerA->firstChild();
500         while (n != c && offsetC < offsetA) {
501             offsetC++;
502             n = n->nextSibling();
503         }
504
505         if (offsetA <= offsetC)
506             return -1;              // A is before B
507         else
508             return 1;               // A is after B
509     }
510
511     // case 3: node C (container A or an ancestor) is a child node of B
512     c = containerA;
513     while (c && c->parentNode() != containerB)
514         c = c->parentNode();
515     if (c) {
516         int offsetC = 0;
517         Node* n = containerB->firstChild();
518         while (n != c && offsetC < offsetB) {
519             offsetC++;
520             n = n->nextSibling();
521         }
522
523         if (offsetC < offsetB)
524             return -1;              // A is before B
525         else
526             return 1;               // A is after B
527     }
528
529     // case 4: containers A & B are siblings, or children of siblings
530     // ### we need to do a traversal here instead
531     Node* commonAncestor = commonAncestorContainer(containerA, containerB);
532     if (!commonAncestor) {
533         ec = WRONG_DOCUMENT_ERR;
534         return 0;
535     }
536     Node* childA = containerA;
537     while (childA && childA->parentNode() != commonAncestor)
538         childA = childA->parentNode();
539     if (!childA)
540         childA = commonAncestor;
541     Node* childB = containerB;
542     while (childB && childB->parentNode() != commonAncestor)
543         childB = childB->parentNode();
544     if (!childB)
545         childB = commonAncestor;
546
547     if (childA == childB)
548         return 0; // A is equal to B
549
550     Node* n = commonAncestor->firstChild();
551     while (n) {
552         if (n == childA)
553             return -1; // A is before B
554         if (n == childB)
555             return 1; // A is after B
556         n = n->nextSibling();
557     }
558
559     // Should never reach this point.
560     ASSERT_NOT_REACHED();
561     return 0;
562 }
563
564 short Range::compareBoundaryPoints(const RangeBoundaryPoint& boundaryA, const RangeBoundaryPoint& boundaryB, ExceptionCode& ec)
565 {
566     return compareBoundaryPoints(boundaryA.container(), boundaryA.offset(), boundaryB.container(), boundaryB.offset(), ec);
567 }
568
569 bool Range::boundaryPointsValid() const
570 {
571     ExceptionCode ec = 0;
572     return m_start.container() && compareBoundaryPoints(m_start, m_end, ec) <= 0 && !ec;
573 }
574
575 void Range::deleteContents(ExceptionCode& ec)
576 {
577     checkDeleteExtract(ec);
578     if (ec)
579         return;
580
581     processContents(Delete, ec);
582 }
583
584 bool Range::intersectsNode(Node* refNode, ExceptionCode& ec)
585 {
586     // http://developer.mozilla.org/en/docs/DOM:range.intersectsNode
587     // Returns a bool if the node intersects the range.
588
589     // Throw exception if the range is already detached.
590     if (!m_start.container()) {
591         ec = INVALID_STATE_ERR;
592         return false;
593     }
594     if (!refNode) {
595         ec = NOT_FOUND_ERR;
596         return false;
597     }
598
599     if (!refNode->inDocument() || &refNode->document() != &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 toCharacterData(node)->length();
666     case Node::PROCESSING_INSTRUCTION_NODE:
667         return toProcessingInstruction(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         return node->childNodeCount();
678     }
679     ASSERT_NOT_REACHED();
680     return 0;
681 }
682
683 PassRefPtr<DocumentFragment> Range::processContents(ActionType action, ExceptionCode& ec)
684 {
685     typedef Vector<RefPtr<Node>> NodeVector;
686
687     RefPtr<DocumentFragment> fragment;
688     if (action == Extract || action == Clone)
689         fragment = DocumentFragment::create(ownerDocument());
690
691     ec = 0;
692     if (collapsed(ec))
693         return fragment.release();
694     if (ec)
695         return 0;
696
697     RefPtr<Node> commonRoot = commonAncestorContainer(ec);
698     if (ec)
699         return 0;
700     ASSERT(commonRoot);
701
702     if (m_start.container() == m_end.container()) {
703         processContentsBetweenOffsets(action, fragment, m_start.container(), m_start.offset(), m_end.offset(), ec);
704         return fragment;
705     }
706
707     // Since mutation events can modify the range during the process, the boundary points need to be saved.
708     RangeBoundaryPoint originalStart(m_start);
709     RangeBoundaryPoint originalEnd(m_end);
710
711     // what is the highest node that partially selects the start / end of the range?
712     RefPtr<Node> partialStart = highestAncestorUnderCommonRoot(originalStart.container(), commonRoot.get());
713     RefPtr<Node> partialEnd = highestAncestorUnderCommonRoot(originalEnd.container(), commonRoot.get());
714
715     // Start and end containers are different.
716     // There are three possibilities here:
717     // 1. Start container == commonRoot (End container must be a descendant)
718     // 2. End container == commonRoot (Start container must be a descendant)
719     // 3. Neither is commonRoot, they are both descendants
720     //
721     // In case 3, we grab everything after the start (up until a direct child
722     // of commonRoot) into leftContents, and everything before the end (up until
723     // a direct child of commonRoot) into rightContents. Then we process all
724     // commonRoot children between leftContents and rightContents
725     //
726     // In case 1 or 2, we skip either processing of leftContents or rightContents,
727     // in which case the last lot of nodes either goes from the first or last
728     // child of commonRoot.
729     //
730     // These are deleted, cloned, or extracted (i.e. both) depending on action.
731
732     // Note that we are verifying that our common root hierarchy is still intact
733     // after any DOM mutation event, at various stages below. See webkit bug 60350.
734
735     RefPtr<Node> leftContents;
736     if (originalStart.container() != commonRoot && commonRoot->contains(originalStart.container())) {
737         leftContents = processContentsBetweenOffsets(action, 0, originalStart.container(), originalStart.offset(), lengthOfContentsInNode(originalStart.container()), ec);
738         leftContents = processAncestorsAndTheirSiblings(action, originalStart.container(), ProcessContentsForward, leftContents, commonRoot.get(), ec);
739     }
740
741     RefPtr<Node> rightContents;
742     if (m_end.container() != commonRoot && commonRoot->contains(originalEnd.container())) {
743         rightContents = processContentsBetweenOffsets(action, 0, originalEnd.container(), 0, originalEnd.offset(), ec);
744         rightContents = processAncestorsAndTheirSiblings(action, originalEnd.container(), ProcessContentsBackward, rightContents, commonRoot.get(), ec);
745     }
746
747     // delete all children of commonRoot between the start and end container
748     RefPtr<Node> processStart = childOfCommonRootBeforeOffset(originalStart.container(), originalStart.offset(), commonRoot.get());
749     if (processStart && originalStart.container() != commonRoot) // processStart contains nodes before m_start.
750         processStart = processStart->nextSibling();
751     RefPtr<Node> processEnd = childOfCommonRootBeforeOffset(originalEnd.container(), originalEnd.offset(), commonRoot.get());
752
753     // Collapse the range, making sure that the result is not within a node that was partially selected.
754     if (action == Extract || action == Delete) {
755         if (partialStart && commonRoot->contains(partialStart.get()))
756             setStart(partialStart->parentNode(), partialStart->nodeIndex() + 1, ec);
757         else if (partialEnd && commonRoot->contains(partialEnd.get()))
758             setStart(partialEnd->parentNode(), partialEnd->nodeIndex(), ec);
759         if (ec)
760             return 0;
761         m_end = m_start;
762     }
763
764     // Now add leftContents, stuff in between, and rightContents to the fragment
765     // (or just delete the stuff in between)
766
767     if ((action == Extract || action == Clone) && leftContents)
768         fragment->appendChild(leftContents, ec);
769
770     if (processStart) {
771         NodeVector nodes;
772         for (Node* n = processStart.get(); n && n != processEnd; n = n->nextSibling())
773             nodes.append(n);
774         processNodes(action, nodes, commonRoot, fragment, ec);
775     }
776
777     if ((action == Extract || action == Clone) && rightContents)
778         fragment->appendChild(rightContents, ec);
779
780     return fragment.release();
781 }
782
783 static inline void deleteCharacterData(PassRefPtr<CharacterData> data, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
784 {
785     if (data->length() - endOffset)
786         data->deleteData(endOffset, data->length() - endOffset, ec);
787     if (startOffset)
788         data->deleteData(0, startOffset, ec);
789 }
790
791 PassRefPtr<Node> Range::processContentsBetweenOffsets(ActionType action, PassRefPtr<DocumentFragment> fragment, Node* container, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
792 {
793     ASSERT(container);
794     ASSERT(startOffset <= endOffset);
795
796     // This switch statement must be consistent with that of lengthOfContentsInNode.
797     RefPtr<Node> result;   
798     switch (container->nodeType()) {
799     case Node::TEXT_NODE:
800     case Node::CDATA_SECTION_NODE:
801     case Node::COMMENT_NODE:
802         endOffset = std::min(endOffset, static_cast<CharacterData*>(container)->length());
803         startOffset = std::min(startOffset, endOffset);
804         if (action == Extract || action == Clone) {
805             RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(container->cloneNode(true));
806             deleteCharacterData(c, startOffset, endOffset, ec);
807             if (fragment) {
808                 result = fragment;
809                 result->appendChild(c.release(), ec);
810             } else
811                 result = c.release();
812         }
813         if (action == Extract || action == Delete)
814             toCharacterData(container)->deleteData(startOffset, endOffset - startOffset, ec);
815         break;
816     case Node::PROCESSING_INSTRUCTION_NODE:
817         endOffset = std::min(endOffset, static_cast<ProcessingInstruction*>(container)->data().length());
818         startOffset = std::min(startOffset, endOffset);
819         if (action == Extract || action == Clone) {
820             RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(container->cloneNode(true));
821             c->setData(c->data().substring(startOffset, endOffset - startOffset), ec);
822             if (fragment) {
823                 result = fragment;
824                 result->appendChild(c.release(), ec);
825             } else
826                 result = c.release();
827         }
828         if (action == Extract || action == Delete) {
829             ProcessingInstruction* pi = toProcessingInstruction(container);
830             String data(pi->data());
831             data.remove(startOffset, endOffset - startOffset);
832             pi->setData(data, ec);
833         }
834         break;
835     case Node::ELEMENT_NODE:
836     case Node::ATTRIBUTE_NODE:
837     case Node::ENTITY_REFERENCE_NODE:
838     case Node::ENTITY_NODE:
839     case Node::DOCUMENT_NODE:
840     case Node::DOCUMENT_TYPE_NODE:
841     case Node::DOCUMENT_FRAGMENT_NODE:
842     case Node::NOTATION_NODE:
843     case Node::XPATH_NAMESPACE_NODE:
844         // FIXME: Should we assert that some nodes never appear here?
845         if (action == Extract || action == Clone) {
846             if (fragment)
847                 result = fragment;
848             else
849                 result = container->cloneNode(false);
850         }
851
852         Node* n = container->firstChild();
853         Vector<RefPtr<Node>> nodes;
854         for (unsigned i = startOffset; n && i; i--)
855             n = n->nextSibling();
856         for (unsigned i = startOffset; n && i < endOffset; i++, n = n->nextSibling())
857             nodes.append(n);
858
859         processNodes(action, nodes, container, result, ec);
860         break;
861     }
862
863     return result.release();
864 }
865
866 void Range::processNodes(ActionType action, Vector<RefPtr<Node>>& nodes, PassRefPtr<Node> oldContainer, PassRefPtr<Node> newContainer, ExceptionCode& ec)
867 {
868     for (unsigned i = 0; i < nodes.size(); i++) {
869         switch (action) {
870         case Delete:
871             oldContainer->removeChild(nodes[i].get(), ec);
872             break;
873         case Extract:
874             newContainer->appendChild(nodes[i].release(), ec); // will remove n from its parent
875             break;
876         case Clone:
877             newContainer->appendChild(nodes[i]->cloneNode(true), ec);
878             break;
879         }
880     }
881 }
882
883 PassRefPtr<Node> Range::processAncestorsAndTheirSiblings(ActionType action, Node* container, ContentsProcessDirection direction, PassRefPtr<Node> passedClonedContainer, Node* commonRoot, ExceptionCode& ec)
884 {
885     typedef Vector<RefPtr<Node>> NodeVector;
886
887     RefPtr<Node> clonedContainer = passedClonedContainer;
888     Vector<RefPtr<Node>> ancestors;
889     for (ContainerNode* n = container->parentNode(); n && n != commonRoot; n = n->parentNode())
890         ancestors.append(n);
891
892     RefPtr<Node> firstChildInAncestorToProcess = direction == ProcessContentsForward ? container->nextSibling() : container->previousSibling();
893     for (Vector<RefPtr<Node>>::const_iterator it = ancestors.begin(); it != ancestors.end(); ++it) {
894         RefPtr<Node> ancestor = *it;
895         if (action == Extract || action == Clone) {
896             if (RefPtr<Node> clonedAncestor = ancestor->cloneNode(false)) { // Might have been removed already during mutation event.
897                 clonedAncestor->appendChild(clonedContainer, ec);
898                 clonedContainer = clonedAncestor;
899             }
900         }
901
902         // Copy siblings of an ancestor of start/end containers
903         // FIXME: This assertion may fail if DOM is modified during mutation event
904         // FIXME: Share code with Range::processNodes
905         ASSERT(!firstChildInAncestorToProcess || firstChildInAncestorToProcess->parentNode() == ancestor);
906         
907         NodeVector nodes;
908         for (Node* child = firstChildInAncestorToProcess.get(); child;
909             child = (direction == ProcessContentsForward) ? child->nextSibling() : child->previousSibling())
910             nodes.append(child);
911
912         for (NodeVector::const_iterator it = nodes.begin(); it != nodes.end(); ++it) {
913             Node* child = it->get();
914             switch (action) {
915             case Delete:
916                 ancestor->removeChild(child, ec);
917                 break;
918             case Extract: // will remove child from ancestor
919                 if (direction == ProcessContentsForward)
920                     clonedContainer->appendChild(child, ec);
921                 else
922                     clonedContainer->insertBefore(child, clonedContainer->firstChild(), ec);
923                 break;
924             case Clone:
925                 if (direction == ProcessContentsForward)
926                     clonedContainer->appendChild(child->cloneNode(true), ec);
927                 else
928                     clonedContainer->insertBefore(child->cloneNode(true), clonedContainer->firstChild(), ec);
929                 break;
930             }
931         }
932         firstChildInAncestorToProcess = direction == ProcessContentsForward ? ancestor->nextSibling() : ancestor->previousSibling();
933     }
934
935     return clonedContainer.release();
936 }
937
938 PassRefPtr<DocumentFragment> Range::extractContents(ExceptionCode& ec)
939 {
940     checkDeleteExtract(ec);
941     if (ec)
942         return 0;
943
944     return processContents(Extract, ec);
945 }
946
947 PassRefPtr<DocumentFragment> Range::cloneContents(ExceptionCode& ec)
948 {
949     if (!m_start.container()) {
950         ec = INVALID_STATE_ERR;
951         return 0;
952     }
953
954     return processContents(Clone, ec);
955 }
956
957 void Range::insertNode(PassRefPtr<Node> prpNewNode, ExceptionCode& ec)
958 {
959     RefPtr<Node> newNode = prpNewNode;
960
961     ec = 0;
962
963     if (!m_start.container()) {
964         ec = INVALID_STATE_ERR;
965         return;
966     }
967
968     if (!newNode) {
969         ec = NOT_FOUND_ERR;
970         return;
971     }
972
973     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
974     // the Range is read-only.
975     if (containedByReadOnly()) {
976         ec = NO_MODIFICATION_ALLOWED_ERR;
977         return;
978     }
979
980     // HIERARCHY_REQUEST_ERR: Raised if the container of the start of the Range is of a type that
981     // does not allow children of the type of newNode or if newNode is an ancestor of the container.
982
983     // an extra one here - if a text node is going to split, it must have a parent to insert into
984     bool startIsText = m_start.container()->isTextNode();
985     if (startIsText && !m_start.container()->parentNode()) {
986         ec = HIERARCHY_REQUEST_ERR;
987         return;
988     }
989
990     // In the case where the container is a text node, we check against the container's parent, because
991     // text nodes get split up upon insertion.
992     Node* checkAgainst;
993     if (startIsText)
994         checkAgainst = m_start.container()->parentNode();
995     else
996         checkAgainst = m_start.container();
997
998     Node::NodeType newNodeType = newNode->nodeType();
999     int numNewChildren;
1000     if (newNodeType == Node::DOCUMENT_FRAGMENT_NODE && !newNode->isShadowRoot()) {
1001         // check each child node, not the DocumentFragment itself
1002         numNewChildren = 0;
1003         for (Node* c = newNode->firstChild(); c; c = c->nextSibling()) {
1004             if (!checkAgainst->childTypeAllowed(c->nodeType())) {
1005                 ec = HIERARCHY_REQUEST_ERR;
1006                 return;
1007             }
1008             ++numNewChildren;
1009         }
1010     } else {
1011         numNewChildren = 1;
1012         if (!checkAgainst->childTypeAllowed(newNodeType)) {
1013             ec = HIERARCHY_REQUEST_ERR;
1014             return;
1015         }
1016     }
1017
1018     for (Node* n = m_start.container(); n; n = n->parentNode()) {
1019         if (n == newNode) {
1020             ec = HIERARCHY_REQUEST_ERR;
1021             return;
1022         }
1023     }
1024
1025     // INVALID_NODE_TYPE_ERR: Raised if newNode is an Attr, Entity, Notation, ShadowRoot or Document node.
1026     switch (newNodeType) {
1027     case Node::ATTRIBUTE_NODE:
1028     case Node::ENTITY_NODE:
1029     case Node::NOTATION_NODE:
1030     case Node::DOCUMENT_NODE:
1031         ec = RangeException::INVALID_NODE_TYPE_ERR;
1032         return;
1033     default:
1034         if (newNode->isShadowRoot()) {
1035             ec = RangeException::INVALID_NODE_TYPE_ERR;
1036             return;
1037         }
1038         break;
1039     }
1040
1041     EventQueueScope scope;
1042     bool collapsed = m_start == m_end;
1043     RefPtr<Node> container;
1044     if (startIsText) {
1045         container = m_start.container();
1046         RefPtr<Text> newText = toText(container.get())->splitText(m_start.offset(), ec);
1047         if (ec)
1048             return;
1049         
1050         container = m_start.container();
1051         container->parentNode()->insertBefore(newNode.release(), newText.get(), ec);
1052         if (ec)
1053             return;
1054
1055         if (collapsed && newText->parentNode() == container && &container->document() == &ownerDocument())
1056             m_end.setToBeforeChild(newText.get());
1057     } else {
1058         container = m_start.container();
1059         RefPtr<Node> firstInsertedChild = newNodeType == Node::DOCUMENT_FRAGMENT_NODE ? newNode->firstChild() : newNode;
1060         RefPtr<Node> lastInsertedChild = newNodeType == Node::DOCUMENT_FRAGMENT_NODE ? newNode->lastChild() : newNode;
1061         RefPtr<Node> childAfterInsertedContent = container->childNode(m_start.offset());
1062         container->insertBefore(newNode.release(), childAfterInsertedContent.get(), ec);
1063         if (ec)
1064             return;
1065
1066         if (collapsed && numNewChildren && &container->document() == &ownerDocument()) {
1067             if (firstInsertedChild->parentNode() == container)
1068                 m_start.setToBeforeChild(firstInsertedChild.get());
1069             if (lastInsertedChild->parentNode() == container)
1070                 m_end.set(container, lastInsertedChild->nodeIndex() + 1, lastInsertedChild.get());
1071         }
1072     }
1073 }
1074
1075 String Range::toString(ExceptionCode& ec) const
1076 {
1077     if (!m_start.container()) {
1078         ec = INVALID_STATE_ERR;
1079         return String();
1080     }
1081
1082     StringBuilder builder;
1083
1084     Node* pastLast = pastLastNode();
1085     for (Node* n = firstNode(); n != pastLast; n = NodeTraversal::next(n)) {
1086         if (n->nodeType() == Node::TEXT_NODE || n->nodeType() == Node::CDATA_SECTION_NODE) {
1087             const String& data = static_cast<CharacterData*>(n)->data();
1088             int length = data.length();
1089             int start = (n == m_start.container()) ? std::min(std::max(0, m_start.offset()), length) : 0;
1090             int end = (n == m_end.container()) ? std::min(std::max(start, m_end.offset()), length) : length;
1091             builder.append(data, start, end - start);
1092         }
1093     }
1094
1095     return builder.toString();
1096 }
1097
1098 String Range::toHTML() const
1099 {
1100     return createMarkup(*this);
1101 }
1102
1103 String Range::text() const
1104 {
1105     if (!m_start.container())
1106         return String();
1107
1108     // We need to update layout, since plainText uses line boxes in the render tree.
1109     // FIXME: As with innerText, we'd like this to work even if there are no render objects.
1110     m_start.container()->document().updateLayout();
1111
1112     return plainText(this);
1113 }
1114
1115 PassRefPtr<DocumentFragment> Range::createContextualFragment(const String& markup, ExceptionCode& ec)
1116 {
1117     if (!m_start.container()) {
1118         ec = INVALID_STATE_ERR;
1119         return 0;
1120     }
1121
1122     Node* element = m_start.container()->isElementNode() ? m_start.container() : m_start.container()->parentNode();
1123     if (!element || !element->isHTMLElement()) {
1124         ec = NOT_SUPPORTED_ERR;
1125         return 0;
1126     }
1127
1128     RefPtr<DocumentFragment> fragment = WebCore::createContextualFragment(markup, toHTMLElement(element), AllowScriptingContentAndDoNotMarkAlreadyStarted, ec);
1129     if (!fragment)
1130         return 0;
1131
1132     return fragment.release();
1133 }
1134
1135
1136 void Range::detach(ExceptionCode& ec)
1137 {
1138     // Check first to see if we've already detached:
1139     if (!m_start.container()) {
1140         ec = INVALID_STATE_ERR;
1141         return;
1142     }
1143
1144     m_ownerDocument->detachRange(this);
1145
1146     m_start.clear();
1147     m_end.clear();
1148 }
1149
1150 Node* Range::checkNodeWOffset(Node* n, int offset, ExceptionCode& ec) const
1151 {
1152     switch (n->nodeType()) {
1153         case Node::DOCUMENT_TYPE_NODE:
1154         case Node::ENTITY_NODE:
1155         case Node::NOTATION_NODE:
1156             ec = RangeException::INVALID_NODE_TYPE_ERR;
1157             return 0;
1158         case Node::CDATA_SECTION_NODE:
1159         case Node::COMMENT_NODE:
1160         case Node::TEXT_NODE:
1161             if (static_cast<unsigned>(offset) > toCharacterData(n)->length())
1162                 ec = INDEX_SIZE_ERR;
1163             return 0;
1164         case Node::PROCESSING_INSTRUCTION_NODE:
1165             if (static_cast<unsigned>(offset) > toProcessingInstruction(n)->data().length())
1166                 ec = INDEX_SIZE_ERR;
1167             return 0;
1168         case Node::ATTRIBUTE_NODE:
1169         case Node::DOCUMENT_FRAGMENT_NODE:
1170         case Node::DOCUMENT_NODE:
1171         case Node::ELEMENT_NODE:
1172         case Node::ENTITY_REFERENCE_NODE:
1173         case Node::XPATH_NAMESPACE_NODE: {
1174             if (!offset)
1175                 return 0;
1176             Node* childBefore = n->childNode(offset - 1);
1177             if (!childBefore)
1178                 ec = INDEX_SIZE_ERR;
1179             return childBefore;
1180         }
1181     }
1182     ASSERT_NOT_REACHED();
1183     return 0;
1184 }
1185
1186 void Range::checkNodeBA(Node* n, ExceptionCode& ec) const
1187 {
1188     // INVALID_NODE_TYPE_ERR: Raised if the root container of refNode is not an
1189     // Attr, Document, DocumentFragment or ShadowRoot node, or part of a SVG shadow DOM tree,
1190     // or if refNode is a Document, DocumentFragment, ShadowRoot, Attr, Entity, or Notation node.
1191
1192     switch (n->nodeType()) {
1193         case Node::ATTRIBUTE_NODE:
1194         case Node::DOCUMENT_FRAGMENT_NODE:
1195         case Node::DOCUMENT_NODE:
1196         case Node::ENTITY_NODE:
1197         case Node::NOTATION_NODE:
1198             ec = RangeException::INVALID_NODE_TYPE_ERR;
1199             return;
1200         case Node::CDATA_SECTION_NODE:
1201         case Node::COMMENT_NODE:
1202         case Node::DOCUMENT_TYPE_NODE:
1203         case Node::ELEMENT_NODE:
1204         case Node::ENTITY_REFERENCE_NODE:
1205         case Node::PROCESSING_INSTRUCTION_NODE:
1206         case Node::TEXT_NODE:
1207         case Node::XPATH_NAMESPACE_NODE:
1208             break;
1209     }
1210
1211     Node* root = n;
1212     while (ContainerNode* parent = root->parentNode())
1213         root = parent;
1214
1215     switch (root->nodeType()) {
1216         case Node::ATTRIBUTE_NODE:
1217         case Node::DOCUMENT_NODE:
1218         case Node::DOCUMENT_FRAGMENT_NODE:
1219             break;
1220         case Node::CDATA_SECTION_NODE:
1221         case Node::COMMENT_NODE:
1222         case Node::DOCUMENT_TYPE_NODE:
1223         case Node::ELEMENT_NODE:
1224         case Node::ENTITY_NODE:
1225         case Node::ENTITY_REFERENCE_NODE:
1226         case Node::NOTATION_NODE:
1227         case Node::PROCESSING_INSTRUCTION_NODE:
1228         case Node::TEXT_NODE:
1229         case Node::XPATH_NAMESPACE_NODE:
1230             ec = RangeException::INVALID_NODE_TYPE_ERR;
1231             return;
1232     }
1233 }
1234
1235 PassRefPtr<Range> Range::cloneRange(ExceptionCode& ec) const
1236 {
1237     if (!m_start.container()) {
1238         ec = INVALID_STATE_ERR;
1239         return 0;
1240     }
1241
1242     return Range::create(ownerDocument(), m_start.container(), m_start.offset(), m_end.container(), m_end.offset());
1243 }
1244
1245 void Range::setStartAfter(Node* refNode, ExceptionCode& ec)
1246 {
1247     if (!m_start.container()) {
1248         ec = INVALID_STATE_ERR;
1249         return;
1250     }
1251
1252     if (!refNode) {
1253         ec = NOT_FOUND_ERR;
1254         return;
1255     }
1256
1257     ec = 0;
1258     checkNodeBA(refNode, ec);
1259     if (ec)
1260         return;
1261
1262     setStart(refNode->parentNode(), refNode->nodeIndex() + 1, ec);
1263 }
1264
1265 void Range::setEndBefore(Node* refNode, ExceptionCode& ec)
1266 {
1267     if (!m_start.container()) {
1268         ec = INVALID_STATE_ERR;
1269         return;
1270     }
1271
1272     if (!refNode) {
1273         ec = NOT_FOUND_ERR;
1274         return;
1275     }
1276
1277     ec = 0;
1278     checkNodeBA(refNode, ec);
1279     if (ec)
1280         return;
1281
1282     setEnd(refNode->parentNode(), refNode->nodeIndex(), ec);
1283 }
1284
1285 void Range::setEndAfter(Node* refNode, ExceptionCode& ec)
1286 {
1287     if (!m_start.container()) {
1288         ec = INVALID_STATE_ERR;
1289         return;
1290     }
1291
1292     if (!refNode) {
1293         ec = NOT_FOUND_ERR;
1294         return;
1295     }
1296
1297     ec = 0;
1298     checkNodeBA(refNode, ec);
1299     if (ec)
1300         return;
1301
1302     setEnd(refNode->parentNode(), refNode->nodeIndex() + 1, ec);
1303 }
1304
1305 void Range::selectNode(Node* refNode, ExceptionCode& ec)
1306 {
1307     if (!m_start.container()) {
1308         ec = INVALID_STATE_ERR;
1309         return;
1310     }
1311
1312     if (!refNode) {
1313         ec = NOT_FOUND_ERR;
1314         return;
1315     }
1316
1317     // INVALID_NODE_TYPE_ERR: Raised if an ancestor of refNode is an Entity, Notation or
1318     // DocumentType node or if refNode is a Document, DocumentFragment, ShadowRoot, Attr, Entity, or Notation
1319     // node.
1320     for (ContainerNode* anc = refNode->parentNode(); anc; anc = anc->parentNode()) {
1321         switch (anc->nodeType()) {
1322             case Node::ATTRIBUTE_NODE:
1323             case Node::CDATA_SECTION_NODE:
1324             case Node::COMMENT_NODE:
1325             case Node::DOCUMENT_FRAGMENT_NODE:
1326             case Node::DOCUMENT_NODE:
1327             case Node::ELEMENT_NODE:
1328             case Node::ENTITY_REFERENCE_NODE:
1329             case Node::PROCESSING_INSTRUCTION_NODE:
1330             case Node::TEXT_NODE:
1331             case Node::XPATH_NAMESPACE_NODE:
1332                 break;
1333             case Node::DOCUMENT_TYPE_NODE:
1334             case Node::ENTITY_NODE:
1335             case Node::NOTATION_NODE:
1336                 ec = RangeException::INVALID_NODE_TYPE_ERR;
1337                 return;
1338         }
1339     }
1340
1341     switch (refNode->nodeType()) {
1342         case Node::CDATA_SECTION_NODE:
1343         case Node::COMMENT_NODE:
1344         case Node::DOCUMENT_TYPE_NODE:
1345         case Node::ELEMENT_NODE:
1346         case Node::ENTITY_REFERENCE_NODE:
1347         case Node::PROCESSING_INSTRUCTION_NODE:
1348         case Node::TEXT_NODE:
1349         case Node::XPATH_NAMESPACE_NODE:
1350             break;
1351         case Node::ATTRIBUTE_NODE:
1352         case Node::DOCUMENT_FRAGMENT_NODE:
1353         case Node::DOCUMENT_NODE:
1354         case Node::ENTITY_NODE:
1355         case Node::NOTATION_NODE:
1356             ec = RangeException::INVALID_NODE_TYPE_ERR;
1357             return;
1358     }
1359
1360     if (&ownerDocument() != &refNode->document())
1361         setDocument(refNode->document());
1362
1363     ec = 0;
1364     setStartBefore(refNode, ec);
1365     if (ec)
1366         return;
1367     setEndAfter(refNode, ec);
1368 }
1369
1370 void Range::selectNodeContents(Node* refNode, ExceptionCode& ec)
1371 {
1372     if (!m_start.container()) {
1373         ec = INVALID_STATE_ERR;
1374         return;
1375     }
1376
1377     if (!refNode) {
1378         ec = NOT_FOUND_ERR;
1379         return;
1380     }
1381
1382     // INVALID_NODE_TYPE_ERR: Raised if refNode or an ancestor of refNode is an Entity, Notation
1383     // or DocumentType node.
1384     for (Node* n = refNode; n; n = n->parentNode()) {
1385         switch (n->nodeType()) {
1386             case Node::ATTRIBUTE_NODE:
1387             case Node::CDATA_SECTION_NODE:
1388             case Node::COMMENT_NODE:
1389             case Node::DOCUMENT_FRAGMENT_NODE:
1390             case Node::DOCUMENT_NODE:
1391             case Node::ELEMENT_NODE:
1392             case Node::ENTITY_REFERENCE_NODE:
1393             case Node::PROCESSING_INSTRUCTION_NODE:
1394             case Node::TEXT_NODE:
1395             case Node::XPATH_NAMESPACE_NODE:
1396                 break;
1397             case Node::DOCUMENT_TYPE_NODE:
1398             case Node::ENTITY_NODE:
1399             case Node::NOTATION_NODE:
1400                 ec = RangeException::INVALID_NODE_TYPE_ERR;
1401                 return;
1402         }
1403     }
1404
1405     if (&ownerDocument() != &refNode->document())
1406         setDocument(refNode->document());
1407
1408     m_start.setToStartOfNode(refNode);
1409     m_end.setToEndOfNode(refNode);
1410 }
1411
1412 void Range::surroundContents(PassRefPtr<Node> passNewParent, ExceptionCode& ec)
1413 {
1414     RefPtr<Node> newParent = passNewParent;
1415
1416     if (!m_start.container()) {
1417         ec = INVALID_STATE_ERR;
1418         return;
1419     }
1420
1421     if (!newParent) {
1422         ec = NOT_FOUND_ERR;
1423         return;
1424     }
1425
1426     // INVALID_NODE_TYPE_ERR: Raised if node is an Attr, Entity, DocumentType, Notation,
1427     // Document, or DocumentFragment node.
1428     switch (newParent->nodeType()) {
1429         case Node::ATTRIBUTE_NODE:
1430         case Node::DOCUMENT_FRAGMENT_NODE:
1431         case Node::DOCUMENT_NODE:
1432         case Node::DOCUMENT_TYPE_NODE:
1433         case Node::ENTITY_NODE:
1434         case Node::NOTATION_NODE:
1435             ec = RangeException::INVALID_NODE_TYPE_ERR;
1436             return;
1437         case Node::CDATA_SECTION_NODE:
1438         case Node::COMMENT_NODE:
1439         case Node::ELEMENT_NODE:
1440         case Node::ENTITY_REFERENCE_NODE:
1441         case Node::PROCESSING_INSTRUCTION_NODE:
1442         case Node::TEXT_NODE:
1443         case Node::XPATH_NAMESPACE_NODE:
1444             break;
1445     }
1446
1447     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
1448     // the Range is read-only.
1449     if (containedByReadOnly()) {
1450         ec = NO_MODIFICATION_ALLOWED_ERR;
1451         return;
1452     }
1453
1454     // Raise a HIERARCHY_REQUEST_ERR if m_start.container() doesn't accept children like newParent.
1455     Node* parentOfNewParent = m_start.container();
1456
1457     // If m_start.container() is a character data node, it will be split and it will be its parent that will 
1458     // need to accept newParent (or in the case of a comment, it logically "would" be inserted into the parent,
1459     // although this will fail below for another reason).
1460     if (parentOfNewParent->isCharacterDataNode())
1461         parentOfNewParent = parentOfNewParent->parentNode();
1462     if (!parentOfNewParent || !parentOfNewParent->childTypeAllowed(newParent->nodeType())) {
1463         ec = HIERARCHY_REQUEST_ERR;
1464         return;
1465     }
1466     
1467     if (newParent->contains(m_start.container())) {
1468         ec = HIERARCHY_REQUEST_ERR;
1469         return;
1470     }
1471
1472     // FIXME: Do we need a check if the node would end up with a child node of a type not
1473     // allowed by the type of node?
1474
1475     // BAD_BOUNDARYPOINTS_ERR: Raised if the Range partially selects a non-Text node.
1476     Node* startNonTextContainer = m_start.container();
1477     if (startNonTextContainer->nodeType() == Node::TEXT_NODE)
1478         startNonTextContainer = startNonTextContainer->parentNode();
1479     Node* endNonTextContainer = m_end.container();
1480     if (endNonTextContainer->nodeType() == Node::TEXT_NODE)
1481         endNonTextContainer = endNonTextContainer->parentNode();
1482     if (startNonTextContainer != endNonTextContainer) {
1483         ec = RangeException::BAD_BOUNDARYPOINTS_ERR;
1484         return;
1485     }
1486
1487     ec = 0;
1488     while (Node* n = newParent->firstChild()) {
1489         toContainerNode(newParent.get())->removeChild(n, ec);
1490         if (ec)
1491             return;
1492     }
1493     RefPtr<DocumentFragment> fragment = extractContents(ec);
1494     if (ec)
1495         return;
1496     insertNode(newParent, ec);
1497     if (ec)
1498         return;
1499     newParent->appendChild(fragment.release(), ec);
1500     if (ec)
1501         return;
1502     selectNode(newParent.get(), ec);
1503 }
1504
1505 void Range::setStartBefore(Node* refNode, ExceptionCode& ec)
1506 {
1507     if (!m_start.container()) {
1508         ec = INVALID_STATE_ERR;
1509         return;
1510     }
1511
1512     if (!refNode) {
1513         ec = NOT_FOUND_ERR;
1514         return;
1515     }
1516
1517     ec = 0;
1518     checkNodeBA(refNode, ec);
1519     if (ec)
1520         return;
1521
1522     setStart(refNode->parentNode(), refNode->nodeIndex(), ec);
1523 }
1524
1525 void Range::checkDeleteExtract(ExceptionCode& ec)
1526 {
1527     if (!m_start.container()) {
1528         ec = INVALID_STATE_ERR;
1529         return;
1530     }
1531
1532     ec = 0;
1533     if (!commonAncestorContainer(ec) || ec)
1534         return;
1535         
1536     Node* pastLast = pastLastNode();
1537     for (Node* n = firstNode(); n != pastLast; n = NodeTraversal::next(n)) {
1538         if (n->isReadOnlyNode()) {
1539             ec = NO_MODIFICATION_ALLOWED_ERR;
1540             return;
1541         }
1542         if (n->nodeType() == Node::DOCUMENT_TYPE_NODE) {
1543             ec = HIERARCHY_REQUEST_ERR;
1544             return;
1545         }
1546     }
1547
1548     if (containedByReadOnly()) {
1549         ec = NO_MODIFICATION_ALLOWED_ERR;
1550         return;
1551     }
1552 }
1553
1554 bool Range::containedByReadOnly() const
1555 {
1556     for (Node* n = m_start.container(); n; n = n->parentNode()) {
1557         if (n->isReadOnlyNode())
1558             return true;
1559     }
1560     for (Node* n = m_end.container(); n; n = n->parentNode()) {
1561         if (n->isReadOnlyNode())
1562             return true;
1563     }
1564     return false;
1565 }
1566
1567 Node* Range::firstNode() const
1568 {
1569     if (!m_start.container())
1570         return 0;
1571     if (m_start.container()->offsetInCharacters())
1572         return m_start.container();
1573     // FIXME: A renderer-based rule is completely out of place here.
1574     // For one thing, the renderer could be out of date if the DOM was recently changed.
1575     if (isRendererReplacedElement(m_start.container()->renderer()))
1576         return m_start.container();
1577     if (Node* child = m_start.container()->childNode(m_start.offset()))
1578         return child;
1579     if (!m_start.offset())
1580         return m_start.container();
1581     return NodeTraversal::nextSkippingChildren(m_start.container());
1582 }
1583
1584 ShadowRoot* Range::shadowRoot() const
1585 {
1586     return startContainer() ? startContainer()->containingShadowRoot() : 0;
1587 }
1588
1589 Node* Range::pastLastNode() const
1590 {
1591     if (!m_start.container() || !m_end.container())
1592         return 0;
1593     if (m_end.container()->offsetInCharacters())
1594         return NodeTraversal::nextSkippingChildren(m_end.container());
1595     if (Node* child = m_end.container()->childNode(m_end.offset()))
1596         return child;
1597     return NodeTraversal::nextSkippingChildren(m_end.container());
1598 }
1599
1600 IntRect Range::boundingBox() const
1601 {
1602     IntRect result;
1603     Vector<IntRect> rects;
1604     textRects(rects);
1605     const size_t n = rects.size();
1606     for (size_t i = 0; i < n; ++i)
1607         result.unite(rects[i]);
1608     return result;
1609 }
1610
1611 void Range::textRects(Vector<IntRect>& rects, bool useSelectionHeight, RangeInFixedPosition* inFixed) const
1612 {
1613     Node* startContainer = m_start.container();
1614     Node* endContainer = m_end.container();
1615
1616     if (!startContainer || !endContainer) {
1617         if (inFixed)
1618             *inFixed = NotFixedPosition;
1619         return;
1620     }
1621
1622     bool allFixed = true;
1623     bool someFixed = false;
1624
1625     Node* stopNode = pastLastNode();
1626     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
1627         RenderObject* r = node->renderer();
1628         if (!r)
1629             continue;
1630         bool isFixed = false;
1631         if (r->isBR())
1632             r->absoluteRects(rects, flooredLayoutPoint(r->localToAbsolute()));
1633         else if (r->isText()) {
1634             int startOffset = node == startContainer ? m_start.offset() : 0;
1635             int endOffset = node == endContainer ? m_end.offset() : std::numeric_limits<int>::max();
1636             rects.appendVector(toRenderText(r)->absoluteRectsForRange(startOffset, endOffset, useSelectionHeight, &isFixed));
1637         } else
1638             continue;
1639         allFixed &= isFixed;
1640         someFixed |= isFixed;
1641     }
1642     
1643     if (inFixed)
1644         *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition);
1645 }
1646
1647 void Range::textQuads(Vector<FloatQuad>& quads, bool useSelectionHeight, RangeInFixedPosition* inFixed) const
1648 {
1649     Node* startContainer = m_start.container();
1650     Node* endContainer = m_end.container();
1651
1652     if (!startContainer || !endContainer) {
1653         if (inFixed)
1654             *inFixed = NotFixedPosition;
1655         return;
1656     }
1657
1658     bool allFixed = true;
1659     bool someFixed = false;
1660
1661     Node* stopNode = pastLastNode();
1662     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
1663         RenderObject* r = node->renderer();
1664         if (!r)
1665             continue;
1666         bool isFixed = false;
1667         if (r->isBR())
1668             r->absoluteQuads(quads, &isFixed);
1669         else if (r->isText()) {
1670             int startOffset = node == startContainer ? m_start.offset() : 0;
1671             int endOffset = node == endContainer ? m_end.offset() : std::numeric_limits<int>::max();
1672             quads.appendVector(toRenderText(r)->absoluteQuadsForRange(startOffset, endOffset, useSelectionHeight, &isFixed));
1673         } else
1674             continue;
1675         allFixed &= isFixed;
1676         someFixed |= isFixed;
1677     }
1678
1679     if (inFixed)
1680         *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition);
1681 }
1682
1683 #if PLATFORM(IOS)
1684 static bool intervalsSufficientlyOverlap(int startA, int endA, int startB, int endB)
1685 {
1686     if (endA <= startA || endB <= startB)
1687         return false;
1688
1689     const float sufficientOverlap = .75;
1690
1691     int lengthA = endA - startA;
1692     int lengthB = endB - startB;
1693
1694     int maxStart = std::max(startA, startB);
1695     int minEnd = std::min(endA, endB);
1696
1697     if (maxStart > minEnd)
1698         return false;
1699
1700     return minEnd - maxStart >= sufficientOverlap * std::min(lengthA, lengthB);
1701 }
1702
1703 static inline void adjustLineHeightOfSelectionRects(Vector<SelectionRect>& rects, size_t numberOfRects, int lineNumber, int lineTop, int lineHeight)
1704 {
1705     ASSERT(rects.size() >= numberOfRects);
1706     for (size_t i = numberOfRects; i; ) {
1707         --i;
1708         if (rects[i].lineNumber())
1709             break;
1710         rects[i].setLineNumber(lineNumber);
1711         rects[i].setLogicalTop(lineTop);
1712         rects[i].setLogicalHeight(lineHeight);
1713     }
1714 }
1715
1716 static SelectionRect coalesceSelectionRects(const SelectionRect& original, const SelectionRect& previous)
1717 {
1718     SelectionRect result(unionRect(previous.rect(), original.rect()), original.isHorizontal(), original.columnNumber());
1719     result.setDirection(original.containsStart() || original.containsEnd() ? original.direction() : previous.direction());
1720     result.setContainsStart(previous.containsStart() || original.containsStart());
1721     result.setContainsEnd(previous.containsEnd() || original.containsEnd());
1722     result.setIsFirstOnLine(previous.isFirstOnLine() || original.isFirstOnLine());
1723     result.setIsLastOnLine(previous.isLastOnLine() || original.isLastOnLine());
1724     return result;
1725 }
1726
1727 // This function is similar in spirit to addLineBoxRects, but annotates the returned rectangles
1728 // with additional state which helps iOS draw selections in its unique way.
1729 void Range::collectSelectionRects(Vector<SelectionRect>& rects)
1730 {
1731     if (!m_start.container() || !m_end.container())
1732         return;
1733
1734     Node* startContainer = m_start.container();
1735     Node* endContainer = m_end.container();
1736     int startOffset = m_start.offset();
1737     int endOffset = m_end.offset();
1738
1739     Vector<SelectionRect> newRects;
1740     Node* stopNode = pastLastNode();
1741     bool hasFlippedWritingMode = startContainer->renderer() && startContainer->renderer()->style().isFlippedBlocksWritingMode();
1742     bool containsDifferentWritingModes = false;
1743     for (Node* node = firstNode(); node && node != stopNode; node = NodeTraversal::next(node)) {
1744         RenderObject* renderer = node->renderer();
1745         // Only ask leaf render objects for their line box rects.
1746         if (renderer && !renderer->firstChildSlow() && renderer->style().userSelect() != SELECT_NONE) {
1747             bool isStartNode = renderer->node() == startContainer;
1748             bool isEndNode = renderer->node() == endContainer;
1749             if (hasFlippedWritingMode != renderer->style().isFlippedBlocksWritingMode())
1750                 containsDifferentWritingModes = true;
1751             // FIXME: Sending 0 for the startOffset is a weird way of telling the renderer that the selection
1752             // doesn't start inside it, since we'll also send 0 if the selection *does* start in it, at offset 0.
1753             //
1754             // FIXME: Selection endpoints aren't always inside leaves, and we only build SelectionRects for leaves,
1755             // so we can't accurately determine which SelectionRects contain the selection start and end using
1756             // only the offsets of the start and end. We need to pass the whole Range.
1757             int beginSelectionOffset = isStartNode ? startOffset : 0;
1758             int endSelectionOffset = isEndNode ? endOffset : std::numeric_limits<int>::max();
1759             renderer->collectSelectionRects(newRects, beginSelectionOffset, endSelectionOffset);
1760             size_t numberOfNewRects = newRects.size();
1761             for (size_t i = 0; i < numberOfNewRects; ++i) {
1762                 SelectionRect& selectionRect = newRects[i];
1763                 if (selectionRect.containsStart() && !isStartNode)
1764                     selectionRect.setContainsStart(false);
1765                 if (selectionRect.containsEnd() && !isEndNode)
1766                     selectionRect.setContainsEnd(false);
1767                 if (selectionRect.logicalWidth() || selectionRect.logicalHeight())
1768                     rects.append(newRects[i]);
1769             }
1770             newRects.shrink(0);
1771         }
1772     }
1773
1774     // The range could span over nodes with different writing modes.
1775     // If this is the case, we use the writing mode of the common ancestor.
1776     if (containsDifferentWritingModes) {
1777         if (Node* ancestor = commonAncestorContainer(startContainer, endContainer))
1778             hasFlippedWritingMode = ancestor->renderer()->style().isFlippedBlocksWritingMode();
1779     }
1780
1781     const size_t numberOfRects = rects.size();
1782
1783     // If the selection ends in a BR, then add the line break bit to the last
1784     // rect we have. This will cause its selection rect to extend to the
1785     // end of the line.
1786     if (stopNode && stopNode->hasTagName(HTMLNames::brTag) && numberOfRects) {
1787         // Only set the line break bit if the end of the range actually
1788         // extends all the way to include the <br>. VisiblePosition helps to
1789         // figure this out.
1790         VisiblePosition endPosition(createLegacyEditingPosition(endContainer, endOffset), VP_DEFAULT_AFFINITY);
1791         VisiblePosition brPosition(createLegacyEditingPosition(stopNode, 0), VP_DEFAULT_AFFINITY);
1792         if (endPosition == brPosition)
1793             rects.last().setIsLineBreak(true);    
1794     }
1795
1796     int lineTop = std::numeric_limits<int>::max();
1797     int lineBottom = std::numeric_limits<int>::min();
1798     int lastLineTop = lineTop;
1799     int lastLineBottom = lineBottom;
1800     int lineNumber = 0;
1801
1802     for (size_t i = 0; i < numberOfRects; ++i) {
1803         int currentRectTop = rects[i].logicalTop();
1804         int currentRectBottom = currentRectTop + rects[i].logicalHeight();
1805
1806         // We don't want to count the ruby text as a separate line.
1807         if (intervalsSufficientlyOverlap(currentRectTop, currentRectBottom, lineTop, lineBottom) || (i && rects[i].isRubyText())) {
1808             // Grow the current line bounds.
1809             lineTop = std::min(lineTop, currentRectTop);
1810             lineBottom = std::max(lineBottom, currentRectBottom);
1811             // Avoid overlap with the previous line.
1812             if (!hasFlippedWritingMode)
1813                 lineTop = std::max(lastLineBottom, lineTop);
1814             else
1815                 lineBottom = std::min(lastLineTop, lineBottom);
1816         } else {
1817             adjustLineHeightOfSelectionRects(rects, i, lineNumber, lineTop, lineBottom - lineTop);
1818             if (!hasFlippedWritingMode) {
1819                 lastLineTop = lineTop;
1820                 if (currentRectBottom >= lastLineTop) {
1821                     lastLineBottom = lineBottom;
1822                     lineTop = lastLineBottom;
1823                 } else {
1824                     lineTop = currentRectTop;
1825                     lastLineBottom = std::numeric_limits<int>::min();
1826                 }
1827                 lineBottom = currentRectBottom;
1828             } else {
1829                 lastLineBottom = lineBottom;
1830                 if (currentRectTop <= lastLineBottom && i && rects[i].columnNumber() == rects[i - 1].columnNumber()) {
1831                     lastLineTop = lineTop;
1832                     lineBottom = lastLineTop;
1833                 } else {
1834                     lastLineTop = std::numeric_limits<int>::max();
1835                     lineBottom = currentRectBottom;
1836                 }
1837                 lineTop = currentRectTop;
1838             }
1839             ++lineNumber;
1840         }
1841     }
1842
1843     // Adjust line height.
1844     adjustLineHeightOfSelectionRects(rects, numberOfRects, lineNumber, lineTop, lineBottom - lineTop);
1845
1846     // Sort the rectangles and make sure there are no gaps. The rectangles could be unsorted when
1847     // there is ruby text and we could have gaps on the line when adjacent elements on the line
1848     // have a different orientation.
1849     size_t firstRectWithCurrentLineNumber = 0;
1850     for (size_t currentRect = 1; currentRect < numberOfRects; ++currentRect) {
1851         if (rects[currentRect].lineNumber() != rects[currentRect - 1].lineNumber()) {
1852             firstRectWithCurrentLineNumber = currentRect;
1853             continue;
1854         }
1855         if (rects[currentRect].logicalLeft() >= rects[currentRect - 1].logicalLeft())
1856             continue;
1857
1858         SelectionRect selectionRect = rects[currentRect];
1859         size_t i;
1860         for (i = currentRect; i > firstRectWithCurrentLineNumber && selectionRect.logicalLeft() < rects[i - 1].logicalLeft(); --i)
1861             rects[i] = rects[i - 1];
1862         rects[i] = selectionRect;
1863     }
1864
1865     for (size_t j = 1; j < numberOfRects; ++j) {
1866         if (rects[j].lineNumber() != rects[j - 1].lineNumber())
1867             continue;
1868         SelectionRect& previousRect = rects[j - 1];
1869         bool previousRectMayNotReachRightEdge = (previousRect.direction() == LTR && previousRect.containsEnd()) || (previousRect.direction() == RTL && previousRect.containsStart());
1870         if (previousRectMayNotReachRightEdge)
1871             continue;
1872         int adjustedWidth = rects[j].logicalLeft() - previousRect.logicalLeft();
1873         if (adjustedWidth > previousRect.logicalWidth())
1874             previousRect.setLogicalWidth(adjustedWidth);
1875     }
1876
1877     int maxLineNumber = lineNumber;
1878
1879     // Extend rects out to edges as needed.
1880     for (size_t i = 0; i < numberOfRects; ++i) {
1881         SelectionRect& selectionRect = rects[i];
1882         if (!selectionRect.isLineBreak() && selectionRect.lineNumber() >= maxLineNumber)
1883             continue;
1884         if (selectionRect.direction() == RTL && selectionRect.isFirstOnLine()) {
1885             selectionRect.setLogicalWidth(selectionRect.logicalWidth() + selectionRect.logicalLeft() - selectionRect.minX());
1886             selectionRect.setLogicalLeft(selectionRect.minX());
1887         } else if (selectionRect.direction() == LTR && selectionRect.isLastOnLine())
1888             selectionRect.setLogicalWidth(selectionRect.maxX() - selectionRect.logicalLeft());
1889     }
1890
1891     // Union all the rectangles on interior lines (i.e. not first or last).
1892     // On first and last lines, just avoid having overlaps by merging intersecting rectangles.
1893     Vector<SelectionRect> unionedRects;
1894     IntRect interiorUnionRect;
1895     for (size_t i = 0; i < numberOfRects; ++i) {
1896         SelectionRect& currentRect = rects[i];
1897         if (currentRect.lineNumber() == 1) {
1898             ASSERT(interiorUnionRect.isEmpty());
1899             if (!unionedRects.isEmpty()) {
1900                 SelectionRect& previousRect = unionedRects.last();
1901                 if (previousRect.rect().intersects(currentRect.rect())) {
1902                     previousRect = coalesceSelectionRects(currentRect, previousRect);
1903                     continue;
1904                 }
1905             }
1906             // Couldn't merge with previous rect, so just appending.
1907             unionedRects.append(currentRect);
1908         } else if (currentRect.lineNumber() < maxLineNumber) {
1909             if (interiorUnionRect.isEmpty()) {
1910                 // Start collecting interior rects.
1911                 interiorUnionRect = currentRect.rect();         
1912             } else if (interiorUnionRect.intersects(currentRect.rect())
1913                 || interiorUnionRect.maxX() == currentRect.rect().x()
1914                 || interiorUnionRect.maxY() == currentRect.rect().y()
1915                 || interiorUnionRect.x() == currentRect.rect().maxX()
1916                 || interiorUnionRect.y() == currentRect.rect().maxY()) {
1917                 // Only union the lines that are attached.
1918                 // For iBooks, the interior lines may cross multiple horizontal pages.
1919                 interiorUnionRect.unite(currentRect.rect());
1920             } else {
1921                 unionedRects.append(SelectionRect(interiorUnionRect, currentRect.isHorizontal(), currentRect.columnNumber()));
1922                 interiorUnionRect = currentRect.rect();
1923             }
1924         } else {
1925             // Processing last line.
1926             if (!interiorUnionRect.isEmpty()) {
1927                 unionedRects.append(SelectionRect(interiorUnionRect, currentRect.isHorizontal(), currentRect.columnNumber()));
1928                 interiorUnionRect = IntRect();
1929             }
1930
1931             ASSERT(!unionedRects.isEmpty());
1932             SelectionRect& previousRect = unionedRects.last();
1933             if (previousRect.logicalTop() == currentRect.logicalTop() && previousRect.rect().intersects(currentRect.rect())) {
1934                 // previousRect is also on the last line, and intersects the current one.
1935                 previousRect = coalesceSelectionRects(currentRect, previousRect);
1936                 continue;
1937             }
1938             // Couldn't merge with previous rect, so just appending.
1939             unionedRects.append(currentRect);
1940         }
1941     }
1942
1943     rects.swap(unionedRects);
1944 }
1945 #endif
1946
1947 #ifndef NDEBUG
1948 void Range::formatForDebugger(char* buffer, unsigned length) const
1949 {
1950     StringBuilder result;
1951     String s;
1952
1953     if (!m_start.container() || !m_end.container())
1954         result.appendLiteral("<empty>");
1955     else {
1956         const int FormatBufferSize = 1024;
1957         char s[FormatBufferSize];
1958         result.appendLiteral("from offset ");
1959         result.appendNumber(m_start.offset());
1960         result.appendLiteral(" of ");
1961         m_start.container()->formatForDebugger(s, FormatBufferSize);
1962         result.append(s);
1963         result.appendLiteral(" to offset ");
1964         result.appendNumber(m_end.offset());
1965         result.appendLiteral(" of ");
1966         m_end.container()->formatForDebugger(s, FormatBufferSize);
1967         result.append(s);
1968     }
1969
1970     strncpy(buffer, result.toString().utf8().data(), length - 1);
1971 }
1972 #endif
1973
1974 bool areRangesEqual(const Range* a, const Range* b)
1975 {
1976     if (a == b)
1977         return true;
1978     if (!a || !b)
1979         return false;
1980     return a->startPosition() == b->startPosition() && a->endPosition() == b->endPosition();
1981 }
1982
1983 PassRefPtr<Range> rangeOfContents(Node& node)
1984 {
1985     RefPtr<Range> range = Range::create(node.document());
1986     int exception = 0;
1987     range->selectNodeContents(&node, exception);
1988     return range.release();
1989 }
1990
1991 int Range::maxStartOffset() const
1992 {
1993     if (!m_start.container())
1994         return 0;
1995     if (!m_start.container()->offsetInCharacters())
1996         return m_start.container()->childNodeCount();
1997     return m_start.container()->maxCharacterOffset();
1998 }
1999
2000 int Range::maxEndOffset() const
2001 {
2002     if (!m_end.container())
2003         return 0;
2004     if (!m_end.container()->offsetInCharacters())
2005         return m_end.container()->childNodeCount();
2006     return m_end.container()->maxCharacterOffset();
2007 }
2008
2009 static inline void boundaryNodeChildrenChanged(RangeBoundaryPoint& boundary, ContainerNode& container)
2010 {
2011     if (!boundary.childBefore())
2012         return;
2013     if (boundary.container() != &container)
2014         return;
2015     boundary.invalidateOffset();
2016 }
2017
2018 void Range::nodeChildrenChanged(ContainerNode& container)
2019 {
2020     ASSERT(&container.document() == &ownerDocument());
2021     boundaryNodeChildrenChanged(m_start, container);
2022     boundaryNodeChildrenChanged(m_end, container);
2023 }
2024
2025 static inline void boundaryNodeChildrenWillBeRemoved(RangeBoundaryPoint& boundary, ContainerNode& container)
2026 {
2027     for (Node* nodeToBeRemoved = container.firstChild(); nodeToBeRemoved; nodeToBeRemoved = nodeToBeRemoved->nextSibling()) {
2028         if (boundary.childBefore() == nodeToBeRemoved) {
2029             boundary.setToStartOfNode(&container);
2030             return;
2031         }
2032
2033         for (Node* n = boundary.container(); n; n = n->parentNode()) {
2034             if (n == nodeToBeRemoved) {
2035                 boundary.setToStartOfNode(&container);
2036                 return;
2037             }
2038         }
2039     }
2040 }
2041
2042 void Range::nodeChildrenWillBeRemoved(ContainerNode& container)
2043 {
2044     ASSERT(&container.document() == &ownerDocument());
2045     boundaryNodeChildrenWillBeRemoved(m_start, container);
2046     boundaryNodeChildrenWillBeRemoved(m_end, container);
2047 }
2048
2049 static inline void boundaryNodeWillBeRemoved(RangeBoundaryPoint& boundary, Node* nodeToBeRemoved)
2050 {
2051     if (boundary.childBefore() == nodeToBeRemoved) {
2052         boundary.childBeforeWillBeRemoved();
2053         return;
2054     }
2055
2056     for (Node* n = boundary.container(); n; n = n->parentNode()) {
2057         if (n == nodeToBeRemoved) {
2058             boundary.setToBeforeChild(nodeToBeRemoved);
2059             return;
2060         }
2061     }
2062 }
2063
2064 void Range::nodeWillBeRemoved(Node* node)
2065 {
2066     ASSERT(node);
2067     ASSERT(&node->document() == &ownerDocument());
2068     ASSERT(node != &ownerDocument());
2069     ASSERT(node->parentNode());
2070     boundaryNodeWillBeRemoved(m_start, node);
2071     boundaryNodeWillBeRemoved(m_end, node);
2072 }
2073
2074 static inline void boundaryTextInserted(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
2075 {
2076     if (boundary.container() != text)
2077         return;
2078     unsigned boundaryOffset = boundary.offset();
2079     if (offset >= boundaryOffset)
2080         return;
2081     boundary.setOffset(boundaryOffset + length);
2082 }
2083
2084 void Range::textInserted(Node* text, unsigned offset, unsigned length)
2085 {
2086     ASSERT(text);
2087     ASSERT(&text->document() == &ownerDocument());
2088     boundaryTextInserted(m_start, text, offset, length);
2089     boundaryTextInserted(m_end, text, offset, length);
2090 }
2091
2092 static inline void boundaryTextRemoved(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
2093 {
2094     if (boundary.container() != text)
2095         return;
2096     unsigned boundaryOffset = boundary.offset();
2097     if (offset >= boundaryOffset)
2098         return;
2099     if (offset + length >= boundaryOffset)
2100         boundary.setOffset(offset);
2101     else
2102         boundary.setOffset(boundaryOffset - length);
2103 }
2104
2105 void Range::textRemoved(Node* text, unsigned offset, unsigned length)
2106 {
2107     ASSERT(text);
2108     ASSERT(&text->document() == &ownerDocument());
2109     boundaryTextRemoved(m_start, text, offset, length);
2110     boundaryTextRemoved(m_end, text, offset, length);
2111 }
2112
2113 static inline void boundaryTextNodesMerged(RangeBoundaryPoint& boundary, NodeWithIndex& oldNode, unsigned offset)
2114 {
2115     if (boundary.container() == oldNode.node())
2116         boundary.set(oldNode.node()->previousSibling(), boundary.offset() + offset, 0);
2117     else if (boundary.container() == oldNode.node()->parentNode() && boundary.offset() == oldNode.index())
2118         boundary.set(oldNode.node()->previousSibling(), offset, 0);
2119 }
2120
2121 void Range::textNodesMerged(NodeWithIndex& oldNode, unsigned offset)
2122 {
2123     ASSERT(oldNode.node());
2124     ASSERT(&oldNode.node()->document() == &ownerDocument());
2125     ASSERT(oldNode.node()->parentNode());
2126     ASSERT(oldNode.node()->isTextNode());
2127     ASSERT(oldNode.node()->previousSibling());
2128     ASSERT(oldNode.node()->previousSibling()->isTextNode());
2129     boundaryTextNodesMerged(m_start, oldNode, offset);
2130     boundaryTextNodesMerged(m_end, oldNode, offset);
2131 }
2132
2133 static inline void boundaryTextNodesSplit(RangeBoundaryPoint& boundary, Text* oldNode)
2134 {
2135     if (boundary.container() != oldNode)
2136         return;
2137     unsigned boundaryOffset = boundary.offset();
2138     if (boundaryOffset <= oldNode->length())
2139         return;
2140     boundary.set(oldNode->nextSibling(), boundaryOffset - oldNode->length(), 0);
2141 }
2142
2143 void Range::textNodeSplit(Text* oldNode)
2144 {
2145     ASSERT(oldNode);
2146     ASSERT(&oldNode->document() == &ownerDocument());
2147     ASSERT(oldNode->parentNode());
2148     ASSERT(oldNode->isTextNode());
2149     ASSERT(oldNode->nextSibling());
2150     ASSERT(oldNode->nextSibling()->isTextNode());
2151     boundaryTextNodesSplit(m_start, oldNode);
2152     boundaryTextNodesSplit(m_end, oldNode);
2153 }
2154
2155 void Range::expand(const String& unit, ExceptionCode& ec)
2156 {
2157     VisiblePosition start(startPosition());
2158     VisiblePosition end(endPosition());
2159     if (unit == "word") {
2160         start = startOfWord(start);
2161         end = endOfWord(end);
2162     } else if (unit == "sentence") {
2163         start = startOfSentence(start);
2164         end = endOfSentence(end);
2165     } else if (unit == "block") {
2166         start = startOfParagraph(start);
2167         end = endOfParagraph(end);
2168     } else if (unit == "document") {
2169         start = startOfDocument(start);
2170         end = endOfDocument(end);
2171     } else
2172         return;
2173     setStart(start.deepEquivalent().containerNode(), start.deepEquivalent().computeOffsetInContainerNode(), ec);
2174     setEnd(end.deepEquivalent().containerNode(), end.deepEquivalent().computeOffsetInContainerNode(), ec);
2175 }
2176
2177 PassRefPtr<ClientRectList> Range::getClientRects() const
2178 {
2179     if (!m_start.container())
2180         return ClientRectList::create();
2181
2182     ownerDocument().updateLayoutIgnorePendingStylesheets();
2183
2184     Vector<FloatQuad> quads;
2185     getBorderAndTextQuads(quads);
2186
2187     return ClientRectList::create(quads);
2188 }
2189
2190 PassRefPtr<ClientRect> Range::getBoundingClientRect() const
2191 {
2192     return ClientRect::create(boundingRect());
2193 }
2194
2195 void Range::getBorderAndTextQuads(Vector<FloatQuad>& quads) const
2196 {
2197     Node* startContainer = m_start.container();
2198     Node* endContainer = m_end.container();
2199     Node* stopNode = pastLastNode();
2200
2201     HashSet<Node*> selectedElementsSet;
2202     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
2203         if (node->isElementNode())
2204             selectedElementsSet.add(node);
2205     }
2206
2207     // Don't include elements that are only partially selected.
2208     Node* lastNode = m_end.childBefore() ? m_end.childBefore() : endContainer;
2209     for (Node* parent = lastNode->parentNode(); parent; parent = parent->parentNode())
2210         selectedElementsSet.remove(parent);
2211
2212     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
2213         if (node->isElementNode() && selectedElementsSet.contains(node) && !selectedElementsSet.contains(node->parentNode())) {
2214             if (RenderBoxModelObject* renderBoxModelObject = toElement(node)->renderBoxModelObject()) {
2215                 Vector<FloatQuad> elementQuads;
2216                 renderBoxModelObject->absoluteQuads(elementQuads);
2217                 ownerDocument().adjustFloatQuadsForScrollAndAbsoluteZoomAndFrameScale(elementQuads, renderBoxModelObject->style());
2218
2219                 quads.appendVector(elementQuads);
2220             }
2221         } else if (node->isTextNode()) {
2222             if (RenderObject* renderer = toText(node)->renderer()) {
2223                 const RenderText& renderText = toRenderText(*renderer);
2224                 int startOffset = (node == startContainer) ? m_start.offset() : 0;
2225                 int endOffset = (node == endContainer) ? m_end.offset() : INT_MAX;
2226                 
2227                 auto textQuads = renderText.absoluteQuadsForRange(startOffset, endOffset);
2228                 ownerDocument().adjustFloatQuadsForScrollAndAbsoluteZoomAndFrameScale(textQuads, renderText.style());
2229
2230                 quads.appendVector(textQuads);
2231             }
2232         }
2233     }
2234 }
2235
2236 FloatRect Range::boundingRect() const
2237 {
2238     if (!m_start.container())
2239         return FloatRect();
2240
2241     ownerDocument().updateLayoutIgnorePendingStylesheets();
2242
2243     Vector<FloatQuad> quads;
2244     getBorderAndTextQuads(quads);
2245     if (quads.isEmpty())
2246         return FloatRect();
2247
2248     FloatRect result;
2249     for (size_t i = 0; i < quads.size(); ++i)
2250         result.unite(quads[i].boundingBox());
2251
2252     return result;
2253 }
2254
2255 } // namespace WebCore
2256
2257 #ifndef NDEBUG
2258
2259 void showTree(const WebCore::Range* range)
2260 {
2261     if (range && range->boundaryPointsValid()) {
2262         range->startContainer()->showTreeAndMark(range->startContainer(), "S", range->endContainer(), "E");
2263         fprintf(stderr, "start offset: %d, end offset: %d\n", range->startOffset(), range->endOffset());
2264     }
2265 }
2266
2267 #endif