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