Use is<>() / downcast<>() for RenderText / RenderTextFragment
[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(downcast<Document>(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     unsigned nodeIndex = refNode->computeNodeIndex();
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     unsigned nodeIndex = refNode->computeNodeIndex();
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     case Node::PROCESSING_INSTRUCTION_NODE:
664         return downcast<CharacterData>(*node).length();
665     case Node::ELEMENT_NODE:
666     case Node::ATTRIBUTE_NODE:
667     case Node::ENTITY_REFERENCE_NODE:
668     case Node::ENTITY_NODE:
669     case Node::DOCUMENT_NODE:
670     case Node::DOCUMENT_TYPE_NODE:
671     case Node::DOCUMENT_FRAGMENT_NODE:
672     case Node::NOTATION_NODE:
673     case Node::XPATH_NAMESPACE_NODE:
674         return node->countChildNodes();
675     }
676     ASSERT_NOT_REACHED();
677     return 0;
678 }
679
680 PassRefPtr<DocumentFragment> Range::processContents(ActionType action, ExceptionCode& ec)
681 {
682     typedef Vector<RefPtr<Node>> NodeVector;
683
684     RefPtr<DocumentFragment> fragment;
685     if (action == Extract || action == Clone)
686         fragment = DocumentFragment::create(ownerDocument());
687
688     ec = 0;
689     if (collapsed(ec))
690         return fragment.release();
691     if (ec)
692         return 0;
693
694     RefPtr<Node> commonRoot = commonAncestorContainer(ec);
695     if (ec)
696         return 0;
697     ASSERT(commonRoot);
698
699     if (m_start.container() == m_end.container()) {
700         processContentsBetweenOffsets(action, fragment, m_start.container(), m_start.offset(), m_end.offset(), ec);
701         return fragment;
702     }
703
704     // Since mutation events can modify the range during the process, the boundary points need to be saved.
705     RangeBoundaryPoint originalStart(m_start);
706     RangeBoundaryPoint originalEnd(m_end);
707
708     // what is the highest node that partially selects the start / end of the range?
709     RefPtr<Node> partialStart = highestAncestorUnderCommonRoot(originalStart.container(), commonRoot.get());
710     RefPtr<Node> partialEnd = highestAncestorUnderCommonRoot(originalEnd.container(), commonRoot.get());
711
712     // Start and end containers are different.
713     // There are three possibilities here:
714     // 1. Start container == commonRoot (End container must be a descendant)
715     // 2. End container == commonRoot (Start container must be a descendant)
716     // 3. Neither is commonRoot, they are both descendants
717     //
718     // In case 3, we grab everything after the start (up until a direct child
719     // of commonRoot) into leftContents, and everything before the end (up until
720     // a direct child of commonRoot) into rightContents. Then we process all
721     // commonRoot children between leftContents and rightContents
722     //
723     // In case 1 or 2, we skip either processing of leftContents or rightContents,
724     // in which case the last lot of nodes either goes from the first or last
725     // child of commonRoot.
726     //
727     // These are deleted, cloned, or extracted (i.e. both) depending on action.
728
729     // Note that we are verifying that our common root hierarchy is still intact
730     // after any DOM mutation event, at various stages below. See webkit bug 60350.
731
732     RefPtr<Node> leftContents;
733     if (originalStart.container() != commonRoot && commonRoot->contains(originalStart.container())) {
734         leftContents = processContentsBetweenOffsets(action, 0, originalStart.container(), originalStart.offset(), lengthOfContentsInNode(originalStart.container()), ec);
735         leftContents = processAncestorsAndTheirSiblings(action, originalStart.container(), ProcessContentsForward, leftContents, commonRoot.get(), ec);
736     }
737
738     RefPtr<Node> rightContents;
739     if (m_end.container() != commonRoot && commonRoot->contains(originalEnd.container())) {
740         rightContents = processContentsBetweenOffsets(action, 0, originalEnd.container(), 0, originalEnd.offset(), ec);
741         rightContents = processAncestorsAndTheirSiblings(action, originalEnd.container(), ProcessContentsBackward, rightContents, commonRoot.get(), ec);
742     }
743
744     // delete all children of commonRoot between the start and end container
745     RefPtr<Node> processStart = childOfCommonRootBeforeOffset(originalStart.container(), originalStart.offset(), commonRoot.get());
746     if (processStart && originalStart.container() != commonRoot) // processStart contains nodes before m_start.
747         processStart = processStart->nextSibling();
748     RefPtr<Node> processEnd = childOfCommonRootBeforeOffset(originalEnd.container(), originalEnd.offset(), commonRoot.get());
749
750     // Collapse the range, making sure that the result is not within a node that was partially selected.
751     if (action == Extract || action == Delete) {
752         if (partialStart && commonRoot->contains(partialStart.get()))
753             setStart(partialStart->parentNode(), partialStart->computeNodeIndex() + 1, ec);
754         else if (partialEnd && commonRoot->contains(partialEnd.get()))
755             setStart(partialEnd->parentNode(), partialEnd->computeNodeIndex(), ec);
756         if (ec)
757             return 0;
758         m_end = m_start;
759     }
760
761     // Now add leftContents, stuff in between, and rightContents to the fragment
762     // (or just delete the stuff in between)
763
764     if ((action == Extract || action == Clone) && leftContents)
765         fragment->appendChild(leftContents, ec);
766
767     if (processStart) {
768         NodeVector nodes;
769         for (Node* n = processStart.get(); n && n != processEnd; n = n->nextSibling())
770             nodes.append(n);
771         processNodes(action, nodes, commonRoot, fragment, ec);
772     }
773
774     if ((action == Extract || action == Clone) && rightContents)
775         fragment->appendChild(rightContents, ec);
776
777     return fragment.release();
778 }
779
780 static inline void deleteCharacterData(PassRefPtr<CharacterData> data, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
781 {
782     if (data->length() - endOffset)
783         data->deleteData(endOffset, data->length() - endOffset, ec);
784     if (startOffset)
785         data->deleteData(0, startOffset, ec);
786 }
787
788 PassRefPtr<Node> Range::processContentsBetweenOffsets(ActionType action, PassRefPtr<DocumentFragment> fragment, Node* container, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
789 {
790     ASSERT(container);
791     ASSERT(startOffset <= endOffset);
792
793     // This switch statement must be consistent with that of lengthOfContentsInNode.
794     RefPtr<Node> result;   
795     switch (container->nodeType()) {
796     case Node::TEXT_NODE:
797     case Node::CDATA_SECTION_NODE:
798     case Node::COMMENT_NODE:
799         endOffset = std::min(endOffset, static_cast<CharacterData*>(container)->length());
800         startOffset = std::min(startOffset, endOffset);
801         if (action == Extract || action == Clone) {
802             RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(container->cloneNode(true));
803             deleteCharacterData(c, startOffset, endOffset, ec);
804             if (fragment) {
805                 result = fragment;
806                 result->appendChild(c.release(), ec);
807             } else
808                 result = c.release();
809         }
810         if (action == Extract || action == Delete)
811             downcast<CharacterData>(*container).deleteData(startOffset, endOffset - startOffset, ec);
812         break;
813     case Node::PROCESSING_INSTRUCTION_NODE:
814         endOffset = std::min(endOffset, static_cast<ProcessingInstruction*>(container)->data().length());
815         startOffset = std::min(startOffset, endOffset);
816         if (action == Extract || action == Clone) {
817             RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(container->cloneNode(true));
818             c->setData(c->data().substring(startOffset, endOffset - startOffset), ec);
819             if (fragment) {
820                 result = fragment;
821                 result->appendChild(c.release(), ec);
822             } else
823                 result = c.release();
824         }
825         if (action == Extract || action == Delete) {
826             ProcessingInstruction& pi = downcast<ProcessingInstruction>(*container);
827             String data(pi.data());
828             data.remove(startOffset, endOffset - startOffset);
829             pi.setData(data, ec);
830         }
831         break;
832     case Node::ELEMENT_NODE:
833     case Node::ATTRIBUTE_NODE:
834     case Node::ENTITY_REFERENCE_NODE:
835     case Node::ENTITY_NODE:
836     case Node::DOCUMENT_NODE:
837     case Node::DOCUMENT_TYPE_NODE:
838     case Node::DOCUMENT_FRAGMENT_NODE:
839     case Node::NOTATION_NODE:
840     case Node::XPATH_NAMESPACE_NODE:
841         // FIXME: Should we assert that some nodes never appear here?
842         if (action == Extract || action == Clone) {
843             if (fragment)
844                 result = fragment;
845             else
846                 result = container->cloneNode(false);
847         }
848
849         Node* n = container->firstChild();
850         Vector<RefPtr<Node>> nodes;
851         for (unsigned i = startOffset; n && i; i--)
852             n = n->nextSibling();
853         for (unsigned i = startOffset; n && i < endOffset; i++, n = n->nextSibling())
854             nodes.append(n);
855
856         processNodes(action, nodes, container, result, ec);
857         break;
858     }
859
860     return result.release();
861 }
862
863 void Range::processNodes(ActionType action, Vector<RefPtr<Node>>& nodes, PassRefPtr<Node> oldContainer, PassRefPtr<Node> newContainer, ExceptionCode& ec)
864 {
865     for (unsigned i = 0; i < nodes.size(); i++) {
866         switch (action) {
867         case Delete:
868             oldContainer->removeChild(nodes[i].get(), ec);
869             break;
870         case Extract:
871             newContainer->appendChild(nodes[i].release(), ec); // will remove n from its parent
872             break;
873         case Clone:
874             newContainer->appendChild(nodes[i]->cloneNode(true), ec);
875             break;
876         }
877     }
878 }
879
880 PassRefPtr<Node> Range::processAncestorsAndTheirSiblings(ActionType action, Node* container, ContentsProcessDirection direction, PassRefPtr<Node> passedClonedContainer, Node* commonRoot, ExceptionCode& ec)
881 {
882     typedef Vector<RefPtr<Node>> NodeVector;
883
884     RefPtr<Node> clonedContainer = passedClonedContainer;
885     Vector<RefPtr<Node>> ancestors;
886     for (ContainerNode* n = container->parentNode(); n && n != commonRoot; n = n->parentNode())
887         ancestors.append(n);
888
889     RefPtr<Node> firstChildInAncestorToProcess = direction == ProcessContentsForward ? container->nextSibling() : container->previousSibling();
890     for (Vector<RefPtr<Node>>::const_iterator it = ancestors.begin(); it != ancestors.end(); ++it) {
891         RefPtr<Node> ancestor = *it;
892         if (action == Extract || action == Clone) {
893             if (RefPtr<Node> clonedAncestor = ancestor->cloneNode(false)) { // Might have been removed already during mutation event.
894                 clonedAncestor->appendChild(clonedContainer, ec);
895                 clonedContainer = clonedAncestor;
896             }
897         }
898
899         // Copy siblings of an ancestor of start/end containers
900         // FIXME: This assertion may fail if DOM is modified during mutation event
901         // FIXME: Share code with Range::processNodes
902         ASSERT(!firstChildInAncestorToProcess || firstChildInAncestorToProcess->parentNode() == ancestor);
903         
904         NodeVector nodes;
905         for (Node* child = firstChildInAncestorToProcess.get(); child;
906             child = (direction == ProcessContentsForward) ? child->nextSibling() : child->previousSibling())
907             nodes.append(child);
908
909         for (NodeVector::const_iterator it = nodes.begin(); it != nodes.end(); ++it) {
910             Node* child = it->get();
911             switch (action) {
912             case Delete:
913                 ancestor->removeChild(child, ec);
914                 break;
915             case Extract: // will remove child from ancestor
916                 if (direction == ProcessContentsForward)
917                     clonedContainer->appendChild(child, ec);
918                 else
919                     clonedContainer->insertBefore(child, clonedContainer->firstChild(), ec);
920                 break;
921             case Clone:
922                 if (direction == ProcessContentsForward)
923                     clonedContainer->appendChild(child->cloneNode(true), ec);
924                 else
925                     clonedContainer->insertBefore(child->cloneNode(true), clonedContainer->firstChild(), ec);
926                 break;
927             }
928         }
929         firstChildInAncestorToProcess = direction == ProcessContentsForward ? ancestor->nextSibling() : ancestor->previousSibling();
930     }
931
932     return clonedContainer.release();
933 }
934
935 PassRefPtr<DocumentFragment> Range::extractContents(ExceptionCode& ec)
936 {
937     checkDeleteExtract(ec);
938     if (ec)
939         return 0;
940
941     return processContents(Extract, ec);
942 }
943
944 PassRefPtr<DocumentFragment> Range::cloneContents(ExceptionCode& ec)
945 {
946     if (!m_start.container()) {
947         ec = INVALID_STATE_ERR;
948         return 0;
949     }
950
951     return processContents(Clone, ec);
952 }
953
954 void Range::insertNode(PassRefPtr<Node> prpNewNode, ExceptionCode& ec)
955 {
956     RefPtr<Node> newNode = prpNewNode;
957
958     ec = 0;
959
960     if (!m_start.container()) {
961         ec = INVALID_STATE_ERR;
962         return;
963     }
964
965     if (!newNode) {
966         ec = NOT_FOUND_ERR;
967         return;
968     }
969
970     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
971     // the Range is read-only.
972     if (containedByReadOnly()) {
973         ec = NO_MODIFICATION_ALLOWED_ERR;
974         return;
975     }
976
977     // HIERARCHY_REQUEST_ERR: Raised if the container of the start of the Range is of a type that
978     // does not allow children of the type of newNode or if newNode is an ancestor of the container.
979
980     // an extra one here - if a text node is going to split, it must have a parent to insert into
981     bool startIsText = is<Text>(*m_start.container());
982     if (startIsText && !m_start.container()->parentNode()) {
983         ec = HIERARCHY_REQUEST_ERR;
984         return;
985     }
986
987     // In the case where the container is a text node, we check against the container's parent, because
988     // text nodes get split up upon insertion.
989     Node* checkAgainst;
990     if (startIsText)
991         checkAgainst = m_start.container()->parentNode();
992     else
993         checkAgainst = m_start.container();
994
995     Node::NodeType newNodeType = newNode->nodeType();
996     int numNewChildren;
997     if (newNodeType == Node::DOCUMENT_FRAGMENT_NODE && !newNode->isShadowRoot()) {
998         // check each child node, not the DocumentFragment itself
999         numNewChildren = 0;
1000         for (Node* c = newNode->firstChild(); c; c = c->nextSibling()) {
1001             if (!checkAgainst->childTypeAllowed(c->nodeType())) {
1002                 ec = HIERARCHY_REQUEST_ERR;
1003                 return;
1004             }
1005             ++numNewChildren;
1006         }
1007     } else {
1008         numNewChildren = 1;
1009         if (!checkAgainst->childTypeAllowed(newNodeType)) {
1010             ec = HIERARCHY_REQUEST_ERR;
1011             return;
1012         }
1013     }
1014
1015     for (Node* n = m_start.container(); n; n = n->parentNode()) {
1016         if (n == newNode) {
1017             ec = HIERARCHY_REQUEST_ERR;
1018             return;
1019         }
1020     }
1021
1022     // INVALID_NODE_TYPE_ERR: Raised if newNode is an Attr, Entity, Notation, ShadowRoot or Document node.
1023     switch (newNodeType) {
1024     case Node::ATTRIBUTE_NODE:
1025     case Node::ENTITY_NODE:
1026     case Node::NOTATION_NODE:
1027     case Node::DOCUMENT_NODE:
1028         ec = RangeException::INVALID_NODE_TYPE_ERR;
1029         return;
1030     default:
1031         if (newNode->isShadowRoot()) {
1032             ec = RangeException::INVALID_NODE_TYPE_ERR;
1033             return;
1034         }
1035         break;
1036     }
1037
1038     EventQueueScope scope;
1039     bool collapsed = m_start == m_end;
1040     RefPtr<Node> container;
1041     if (startIsText) {
1042         container = m_start.container();
1043         RefPtr<Text> newText = downcast<Text>(*container).splitText(m_start.offset(), ec);
1044         if (ec)
1045             return;
1046         
1047         container = m_start.container();
1048         container->parentNode()->insertBefore(newNode.release(), newText.get(), ec);
1049         if (ec)
1050             return;
1051
1052         if (collapsed && newText->parentNode() == container && &container->document() == &ownerDocument())
1053             m_end.setToBeforeChild(newText.get());
1054     } else {
1055         container = m_start.container();
1056         RefPtr<Node> firstInsertedChild = newNodeType == Node::DOCUMENT_FRAGMENT_NODE ? newNode->firstChild() : newNode;
1057         RefPtr<Node> lastInsertedChild = newNodeType == Node::DOCUMENT_FRAGMENT_NODE ? newNode->lastChild() : newNode;
1058         RefPtr<Node> childAfterInsertedContent = container->traverseToChildAt(m_start.offset());
1059         container->insertBefore(newNode.release(), childAfterInsertedContent.get(), ec);
1060         if (ec)
1061             return;
1062
1063         if (collapsed && numNewChildren && &container->document() == &ownerDocument()) {
1064             if (firstInsertedChild->parentNode() == container)
1065                 m_start.setToBeforeChild(firstInsertedChild.get());
1066             if (lastInsertedChild->parentNode() == container)
1067                 m_end.set(container, lastInsertedChild->computeNodeIndex() + 1, lastInsertedChild.get());
1068         }
1069     }
1070 }
1071
1072 String Range::toString(ExceptionCode& ec) const
1073 {
1074     if (!m_start.container()) {
1075         ec = INVALID_STATE_ERR;
1076         return String();
1077     }
1078
1079     StringBuilder builder;
1080
1081     Node* pastLast = pastLastNode();
1082     for (Node* n = firstNode(); n != pastLast; n = NodeTraversal::next(n)) {
1083         if (n->nodeType() == Node::TEXT_NODE || n->nodeType() == Node::CDATA_SECTION_NODE) {
1084             const String& data = static_cast<CharacterData*>(n)->data();
1085             int length = data.length();
1086             int start = (n == m_start.container()) ? std::min(std::max(0, m_start.offset()), length) : 0;
1087             int end = (n == m_end.container()) ? std::min(std::max(start, m_end.offset()), length) : length;
1088             builder.append(data, start, end - start);
1089         }
1090     }
1091
1092     return builder.toString();
1093 }
1094
1095 String Range::toHTML() const
1096 {
1097     return createMarkup(*this);
1098 }
1099
1100 String Range::text() const
1101 {
1102     if (!m_start.container())
1103         return String();
1104
1105     // We need to update layout, since plainText uses line boxes in the render tree.
1106     // FIXME: As with innerText, we'd like this to work even if there are no render objects.
1107     m_start.container()->document().updateLayout();
1108
1109     return plainText(this);
1110 }
1111
1112 PassRefPtr<DocumentFragment> Range::createContextualFragment(const String& markup, ExceptionCode& ec)
1113 {
1114     if (!m_start.container()) {
1115         ec = INVALID_STATE_ERR;
1116         return 0;
1117     }
1118
1119     Node* element = m_start.container()->isElementNode() ? m_start.container() : m_start.container()->parentNode();
1120     if (!element || !element->isHTMLElement()) {
1121         ec = NOT_SUPPORTED_ERR;
1122         return 0;
1123     }
1124
1125     RefPtr<DocumentFragment> fragment = WebCore::createContextualFragment(markup, downcast<HTMLElement>(element), AllowScriptingContentAndDoNotMarkAlreadyStarted, ec);
1126     if (!fragment)
1127         return 0;
1128
1129     return fragment.release();
1130 }
1131
1132
1133 void Range::detach(ExceptionCode& ec)
1134 {
1135     // Check first to see if we've already detached:
1136     if (!m_start.container()) {
1137         ec = INVALID_STATE_ERR;
1138         return;
1139     }
1140
1141     m_ownerDocument->detachRange(this);
1142
1143     m_start.clear();
1144     m_end.clear();
1145 }
1146
1147 Node* Range::checkNodeWOffset(Node* n, int offset, ExceptionCode& ec) const
1148 {
1149     switch (n->nodeType()) {
1150         case Node::DOCUMENT_TYPE_NODE:
1151         case Node::ENTITY_NODE:
1152         case Node::NOTATION_NODE:
1153             ec = RangeException::INVALID_NODE_TYPE_ERR;
1154             return nullptr;
1155         case Node::CDATA_SECTION_NODE:
1156         case Node::COMMENT_NODE:
1157         case Node::TEXT_NODE:
1158         case Node::PROCESSING_INSTRUCTION_NODE:
1159             if (static_cast<unsigned>(offset) > downcast<CharacterData>(*n).length())
1160                 ec = INDEX_SIZE_ERR;
1161             return nullptr;
1162         case Node::ATTRIBUTE_NODE:
1163         case Node::DOCUMENT_FRAGMENT_NODE:
1164         case Node::DOCUMENT_NODE:
1165         case Node::ELEMENT_NODE:
1166         case Node::ENTITY_REFERENCE_NODE:
1167         case Node::XPATH_NAMESPACE_NODE: {
1168             if (!offset)
1169                 return nullptr;
1170             Node* childBefore = n->traverseToChildAt(offset - 1);
1171             if (!childBefore)
1172                 ec = INDEX_SIZE_ERR;
1173             return childBefore;
1174         }
1175     }
1176     ASSERT_NOT_REACHED();
1177     return nullptr;
1178 }
1179
1180 void Range::checkNodeBA(Node* n, ExceptionCode& ec) const
1181 {
1182     // INVALID_NODE_TYPE_ERR: Raised if the root container of refNode is not an
1183     // Attr, Document, DocumentFragment or ShadowRoot node, or part of a SVG shadow DOM tree,
1184     // or if refNode is a Document, DocumentFragment, ShadowRoot, Attr, Entity, or Notation node.
1185
1186     switch (n->nodeType()) {
1187         case Node::ATTRIBUTE_NODE:
1188         case Node::DOCUMENT_FRAGMENT_NODE:
1189         case Node::DOCUMENT_NODE:
1190         case Node::ENTITY_NODE:
1191         case Node::NOTATION_NODE:
1192             ec = RangeException::INVALID_NODE_TYPE_ERR;
1193             return;
1194         case Node::CDATA_SECTION_NODE:
1195         case Node::COMMENT_NODE:
1196         case Node::DOCUMENT_TYPE_NODE:
1197         case Node::ELEMENT_NODE:
1198         case Node::ENTITY_REFERENCE_NODE:
1199         case Node::PROCESSING_INSTRUCTION_NODE:
1200         case Node::TEXT_NODE:
1201         case Node::XPATH_NAMESPACE_NODE:
1202             break;
1203     }
1204
1205     Node* root = n;
1206     while (ContainerNode* parent = root->parentNode())
1207         root = parent;
1208
1209     switch (root->nodeType()) {
1210         case Node::ATTRIBUTE_NODE:
1211         case Node::DOCUMENT_NODE:
1212         case Node::DOCUMENT_FRAGMENT_NODE:
1213             break;
1214         case Node::CDATA_SECTION_NODE:
1215         case Node::COMMENT_NODE:
1216         case Node::DOCUMENT_TYPE_NODE:
1217         case Node::ELEMENT_NODE:
1218         case Node::ENTITY_NODE:
1219         case Node::ENTITY_REFERENCE_NODE:
1220         case Node::NOTATION_NODE:
1221         case Node::PROCESSING_INSTRUCTION_NODE:
1222         case Node::TEXT_NODE:
1223         case Node::XPATH_NAMESPACE_NODE:
1224             ec = RangeException::INVALID_NODE_TYPE_ERR;
1225             return;
1226     }
1227 }
1228
1229 PassRefPtr<Range> Range::cloneRange(ExceptionCode& ec) const
1230 {
1231     if (!m_start.container()) {
1232         ec = INVALID_STATE_ERR;
1233         return 0;
1234     }
1235
1236     return Range::create(ownerDocument(), m_start.container(), m_start.offset(), m_end.container(), m_end.offset());
1237 }
1238
1239 void Range::setStartAfter(Node* refNode, ExceptionCode& ec)
1240 {
1241     if (!m_start.container()) {
1242         ec = INVALID_STATE_ERR;
1243         return;
1244     }
1245
1246     if (!refNode) {
1247         ec = NOT_FOUND_ERR;
1248         return;
1249     }
1250
1251     ec = 0;
1252     checkNodeBA(refNode, ec);
1253     if (ec)
1254         return;
1255
1256     setStart(refNode->parentNode(), refNode->computeNodeIndex() + 1, ec);
1257 }
1258
1259 void Range::setEndBefore(Node* refNode, ExceptionCode& ec)
1260 {
1261     if (!m_start.container()) {
1262         ec = INVALID_STATE_ERR;
1263         return;
1264     }
1265
1266     if (!refNode) {
1267         ec = NOT_FOUND_ERR;
1268         return;
1269     }
1270
1271     ec = 0;
1272     checkNodeBA(refNode, ec);
1273     if (ec)
1274         return;
1275
1276     setEnd(refNode->parentNode(), refNode->computeNodeIndex(), ec);
1277 }
1278
1279 void Range::setEndAfter(Node* refNode, ExceptionCode& ec)
1280 {
1281     if (!m_start.container()) {
1282         ec = INVALID_STATE_ERR;
1283         return;
1284     }
1285
1286     if (!refNode) {
1287         ec = NOT_FOUND_ERR;
1288         return;
1289     }
1290
1291     ec = 0;
1292     checkNodeBA(refNode, ec);
1293     if (ec)
1294         return;
1295
1296     setEnd(refNode->parentNode(), refNode->computeNodeIndex() + 1, ec);
1297 }
1298
1299 void Range::selectNode(Node* refNode, ExceptionCode& ec)
1300 {
1301     if (!m_start.container()) {
1302         ec = INVALID_STATE_ERR;
1303         return;
1304     }
1305
1306     if (!refNode) {
1307         ec = NOT_FOUND_ERR;
1308         return;
1309     }
1310
1311     // INVALID_NODE_TYPE_ERR: Raised if an ancestor of refNode is an Entity, Notation or
1312     // DocumentType node or if refNode is a Document, DocumentFragment, ShadowRoot, Attr, Entity, or Notation
1313     // node.
1314     for (ContainerNode* anc = refNode->parentNode(); anc; anc = anc->parentNode()) {
1315         switch (anc->nodeType()) {
1316             case Node::ATTRIBUTE_NODE:
1317             case Node::CDATA_SECTION_NODE:
1318             case Node::COMMENT_NODE:
1319             case Node::DOCUMENT_FRAGMENT_NODE:
1320             case Node::DOCUMENT_NODE:
1321             case Node::ELEMENT_NODE:
1322             case Node::ENTITY_REFERENCE_NODE:
1323             case Node::PROCESSING_INSTRUCTION_NODE:
1324             case Node::TEXT_NODE:
1325             case Node::XPATH_NAMESPACE_NODE:
1326                 break;
1327             case Node::DOCUMENT_TYPE_NODE:
1328             case Node::ENTITY_NODE:
1329             case Node::NOTATION_NODE:
1330                 ec = RangeException::INVALID_NODE_TYPE_ERR;
1331                 return;
1332         }
1333     }
1334
1335     switch (refNode->nodeType()) {
1336         case Node::CDATA_SECTION_NODE:
1337         case Node::COMMENT_NODE:
1338         case Node::DOCUMENT_TYPE_NODE:
1339         case Node::ELEMENT_NODE:
1340         case Node::ENTITY_REFERENCE_NODE:
1341         case Node::PROCESSING_INSTRUCTION_NODE:
1342         case Node::TEXT_NODE:
1343         case Node::XPATH_NAMESPACE_NODE:
1344             break;
1345         case Node::ATTRIBUTE_NODE:
1346         case Node::DOCUMENT_FRAGMENT_NODE:
1347         case Node::DOCUMENT_NODE:
1348         case Node::ENTITY_NODE:
1349         case Node::NOTATION_NODE:
1350             ec = RangeException::INVALID_NODE_TYPE_ERR;
1351             return;
1352     }
1353
1354     if (&ownerDocument() != &refNode->document())
1355         setDocument(refNode->document());
1356
1357     ec = 0;
1358     setStartBefore(refNode, ec);
1359     if (ec)
1360         return;
1361     setEndAfter(refNode, ec);
1362 }
1363
1364 void Range::selectNodeContents(Node* refNode, ExceptionCode& ec)
1365 {
1366     if (!m_start.container()) {
1367         ec = INVALID_STATE_ERR;
1368         return;
1369     }
1370
1371     if (!refNode) {
1372         ec = NOT_FOUND_ERR;
1373         return;
1374     }
1375
1376     // INVALID_NODE_TYPE_ERR: Raised if refNode or an ancestor of refNode is an Entity, Notation
1377     // or DocumentType node.
1378     for (Node* n = refNode; n; n = n->parentNode()) {
1379         switch (n->nodeType()) {
1380             case Node::ATTRIBUTE_NODE:
1381             case Node::CDATA_SECTION_NODE:
1382             case Node::COMMENT_NODE:
1383             case Node::DOCUMENT_FRAGMENT_NODE:
1384             case Node::DOCUMENT_NODE:
1385             case Node::ELEMENT_NODE:
1386             case Node::ENTITY_REFERENCE_NODE:
1387             case Node::PROCESSING_INSTRUCTION_NODE:
1388             case Node::TEXT_NODE:
1389             case Node::XPATH_NAMESPACE_NODE:
1390                 break;
1391             case Node::DOCUMENT_TYPE_NODE:
1392             case Node::ENTITY_NODE:
1393             case Node::NOTATION_NODE:
1394                 ec = RangeException::INVALID_NODE_TYPE_ERR;
1395                 return;
1396         }
1397     }
1398
1399     if (&ownerDocument() != &refNode->document())
1400         setDocument(refNode->document());
1401
1402     m_start.setToStartOfNode(refNode);
1403     m_end.setToEndOfNode(refNode);
1404 }
1405
1406 void Range::surroundContents(PassRefPtr<Node> passNewParent, ExceptionCode& ec)
1407 {
1408     RefPtr<Node> newParent = passNewParent;
1409
1410     if (!m_start.container()) {
1411         ec = INVALID_STATE_ERR;
1412         return;
1413     }
1414
1415     if (!newParent) {
1416         ec = NOT_FOUND_ERR;
1417         return;
1418     }
1419
1420     // INVALID_NODE_TYPE_ERR: Raised if node is an Attr, Entity, DocumentType, Notation,
1421     // Document, or DocumentFragment node.
1422     switch (newParent->nodeType()) {
1423         case Node::ATTRIBUTE_NODE:
1424         case Node::DOCUMENT_FRAGMENT_NODE:
1425         case Node::DOCUMENT_NODE:
1426         case Node::DOCUMENT_TYPE_NODE:
1427         case Node::ENTITY_NODE:
1428         case Node::NOTATION_NODE:
1429             ec = RangeException::INVALID_NODE_TYPE_ERR;
1430             return;
1431         case Node::CDATA_SECTION_NODE:
1432         case Node::COMMENT_NODE:
1433         case Node::ELEMENT_NODE:
1434         case Node::ENTITY_REFERENCE_NODE:
1435         case Node::PROCESSING_INSTRUCTION_NODE:
1436         case Node::TEXT_NODE:
1437         case Node::XPATH_NAMESPACE_NODE:
1438             break;
1439     }
1440
1441     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
1442     // the Range is read-only.
1443     if (containedByReadOnly()) {
1444         ec = NO_MODIFICATION_ALLOWED_ERR;
1445         return;
1446     }
1447
1448     // Raise a HIERARCHY_REQUEST_ERR if m_start.container() doesn't accept children like newParent.
1449     Node* parentOfNewParent = m_start.container();
1450
1451     // If m_start.container() is a character data node, it will be split and it will be its parent that will 
1452     // need to accept newParent (or in the case of a comment, it logically "would" be inserted into the parent,
1453     // although this will fail below for another reason).
1454     if (parentOfNewParent->isCharacterDataNode())
1455         parentOfNewParent = parentOfNewParent->parentNode();
1456     if (!parentOfNewParent || !parentOfNewParent->childTypeAllowed(newParent->nodeType())) {
1457         ec = HIERARCHY_REQUEST_ERR;
1458         return;
1459     }
1460     
1461     if (newParent->contains(m_start.container())) {
1462         ec = HIERARCHY_REQUEST_ERR;
1463         return;
1464     }
1465
1466     // FIXME: Do we need a check if the node would end up with a child node of a type not
1467     // allowed by the type of node?
1468
1469     // BAD_BOUNDARYPOINTS_ERR: Raised if the Range partially selects a non-Text node.
1470     Node* startNonTextContainer = m_start.container();
1471     if (startNonTextContainer->nodeType() == Node::TEXT_NODE)
1472         startNonTextContainer = startNonTextContainer->parentNode();
1473     Node* endNonTextContainer = m_end.container();
1474     if (endNonTextContainer->nodeType() == Node::TEXT_NODE)
1475         endNonTextContainer = endNonTextContainer->parentNode();
1476     if (startNonTextContainer != endNonTextContainer) {
1477         ec = RangeException::BAD_BOUNDARYPOINTS_ERR;
1478         return;
1479     }
1480
1481     ec = 0;
1482     while (Node* n = newParent->firstChild()) {
1483         downcast<ContainerNode>(*newParent).removeChild(n, ec);
1484         if (ec)
1485             return;
1486     }
1487     RefPtr<DocumentFragment> fragment = extractContents(ec);
1488     if (ec)
1489         return;
1490     insertNode(newParent, ec);
1491     if (ec)
1492         return;
1493     newParent->appendChild(fragment.release(), ec);
1494     if (ec)
1495         return;
1496     selectNode(newParent.get(), ec);
1497 }
1498
1499 void Range::setStartBefore(Node* refNode, ExceptionCode& ec)
1500 {
1501     if (!m_start.container()) {
1502         ec = INVALID_STATE_ERR;
1503         return;
1504     }
1505
1506     if (!refNode) {
1507         ec = NOT_FOUND_ERR;
1508         return;
1509     }
1510
1511     ec = 0;
1512     checkNodeBA(refNode, ec);
1513     if (ec)
1514         return;
1515
1516     setStart(refNode->parentNode(), refNode->computeNodeIndex(), ec);
1517 }
1518
1519 void Range::checkDeleteExtract(ExceptionCode& ec)
1520 {
1521     if (!m_start.container()) {
1522         ec = INVALID_STATE_ERR;
1523         return;
1524     }
1525
1526     ec = 0;
1527     if (!commonAncestorContainer(ec) || ec)
1528         return;
1529         
1530     Node* pastLast = pastLastNode();
1531     for (Node* n = firstNode(); n != pastLast; n = NodeTraversal::next(n)) {
1532         if (n->isReadOnlyNode()) {
1533             ec = NO_MODIFICATION_ALLOWED_ERR;
1534             return;
1535         }
1536         if (n->nodeType() == Node::DOCUMENT_TYPE_NODE) {
1537             ec = HIERARCHY_REQUEST_ERR;
1538             return;
1539         }
1540     }
1541
1542     if (containedByReadOnly()) {
1543         ec = NO_MODIFICATION_ALLOWED_ERR;
1544         return;
1545     }
1546 }
1547
1548 bool Range::containedByReadOnly() const
1549 {
1550     for (Node* n = m_start.container(); n; n = n->parentNode()) {
1551         if (n->isReadOnlyNode())
1552             return true;
1553     }
1554     for (Node* n = m_end.container(); n; n = n->parentNode()) {
1555         if (n->isReadOnlyNode())
1556             return true;
1557     }
1558     return false;
1559 }
1560
1561 Node* Range::firstNode() const
1562 {
1563     if (!m_start.container())
1564         return 0;
1565     if (m_start.container()->offsetInCharacters())
1566         return m_start.container();
1567     if (Node* child = m_start.container()->traverseToChildAt(m_start.offset()))
1568         return child;
1569     if (!m_start.offset())
1570         return m_start.container();
1571     return NodeTraversal::nextSkippingChildren(m_start.container());
1572 }
1573
1574 ShadowRoot* Range::shadowRoot() const
1575 {
1576     return startContainer() ? startContainer()->containingShadowRoot() : 0;
1577 }
1578
1579 Node* Range::pastLastNode() const
1580 {
1581     if (!m_start.container() || !m_end.container())
1582         return 0;
1583     if (m_end.container()->offsetInCharacters())
1584         return NodeTraversal::nextSkippingChildren(m_end.container());
1585     if (Node* child = m_end.container()->traverseToChildAt(m_end.offset()))
1586         return child;
1587     return NodeTraversal::nextSkippingChildren(m_end.container());
1588 }
1589
1590 IntRect Range::boundingBox() const
1591 {
1592     IntRect result;
1593     Vector<IntRect> rects;
1594     textRects(rects);
1595     const size_t n = rects.size();
1596     for (size_t i = 0; i < n; ++i)
1597         result.unite(rects[i]);
1598     return result;
1599 }
1600
1601 void Range::textRects(Vector<IntRect>& rects, bool useSelectionHeight, RangeInFixedPosition* inFixed) const
1602 {
1603     Node* startContainer = m_start.container();
1604     Node* endContainer = m_end.container();
1605
1606     if (!startContainer || !endContainer) {
1607         if (inFixed)
1608             *inFixed = NotFixedPosition;
1609         return;
1610     }
1611
1612     bool allFixed = true;
1613     bool someFixed = false;
1614
1615     Node* stopNode = pastLastNode();
1616     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
1617         RenderObject* renderer = node->renderer();
1618         if (!renderer)
1619             continue;
1620         bool isFixed = false;
1621         if (renderer->isBR())
1622             renderer->absoluteRects(rects, flooredLayoutPoint(renderer->localToAbsolute()));
1623         else if (is<RenderText>(*renderer)) {
1624             int startOffset = node == startContainer ? m_start.offset() : 0;
1625             int endOffset = node == endContainer ? m_end.offset() : std::numeric_limits<int>::max();
1626             rects.appendVector(downcast<RenderText>(*renderer).absoluteRectsForRange(startOffset, endOffset, useSelectionHeight, &isFixed));
1627         } else
1628             continue;
1629         allFixed &= isFixed;
1630         someFixed |= isFixed;
1631     }
1632     
1633     if (inFixed)
1634         *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition);
1635 }
1636
1637 void Range::textQuads(Vector<FloatQuad>& quads, bool useSelectionHeight, RangeInFixedPosition* inFixed) const
1638 {
1639     Node* startContainer = m_start.container();
1640     Node* endContainer = m_end.container();
1641
1642     if (!startContainer || !endContainer) {
1643         if (inFixed)
1644             *inFixed = NotFixedPosition;
1645         return;
1646     }
1647
1648     bool allFixed = true;
1649     bool someFixed = false;
1650
1651     Node* stopNode = pastLastNode();
1652     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
1653         RenderObject* renderer = node->renderer();
1654         if (!renderer)
1655             continue;
1656         bool isFixed = false;
1657         if (renderer->isBR())
1658             renderer->absoluteQuads(quads, &isFixed);
1659         else if (is<RenderText>(*renderer)) {
1660             int startOffset = node == startContainer ? m_start.offset() : 0;
1661             int endOffset = node == endContainer ? m_end.offset() : std::numeric_limits<int>::max();
1662             quads.appendVector(downcast<RenderText>(*renderer).absoluteQuadsForRange(startOffset, endOffset, useSelectionHeight, &isFixed));
1663         } else
1664             continue;
1665         allFixed &= isFixed;
1666         someFixed |= isFixed;
1667     }
1668
1669     if (inFixed)
1670         *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition);
1671 }
1672
1673 #if PLATFORM(IOS)
1674 static bool intervalsSufficientlyOverlap(int startA, int endA, int startB, int endB)
1675 {
1676     if (endA <= startA || endB <= startB)
1677         return false;
1678
1679     const float sufficientOverlap = .75;
1680
1681     int lengthA = endA - startA;
1682     int lengthB = endB - startB;
1683
1684     int maxStart = std::max(startA, startB);
1685     int minEnd = std::min(endA, endB);
1686
1687     if (maxStart > minEnd)
1688         return false;
1689
1690     return minEnd - maxStart >= sufficientOverlap * std::min(lengthA, lengthB);
1691 }
1692
1693 static inline void adjustLineHeightOfSelectionRects(Vector<SelectionRect>& rects, size_t numberOfRects, int lineNumber, int lineTop, int lineHeight)
1694 {
1695     ASSERT(rects.size() >= numberOfRects);
1696     for (size_t i = numberOfRects; i; ) {
1697         --i;
1698         if (rects[i].lineNumber())
1699             break;
1700         rects[i].setLineNumber(lineNumber);
1701         rects[i].setLogicalTop(lineTop);
1702         rects[i].setLogicalHeight(lineHeight);
1703     }
1704 }
1705
1706 static SelectionRect coalesceSelectionRects(const SelectionRect& original, const SelectionRect& previous)
1707 {
1708     SelectionRect result(unionRect(previous.rect(), original.rect()), original.isHorizontal(), original.pageNumber());
1709     result.setDirection(original.containsStart() || original.containsEnd() ? original.direction() : previous.direction());
1710     result.setContainsStart(previous.containsStart() || original.containsStart());
1711     result.setContainsEnd(previous.containsEnd() || original.containsEnd());
1712     result.setIsFirstOnLine(previous.isFirstOnLine() || original.isFirstOnLine());
1713     result.setIsLastOnLine(previous.isLastOnLine() || original.isLastOnLine());
1714     return result;
1715 }
1716
1717 // This function is similar in spirit to addLineBoxRects, but annotates the returned rectangles
1718 // with additional state which helps iOS draw selections in its unique way.
1719 void Range::collectSelectionRects(Vector<SelectionRect>& rects)
1720 {
1721     if (!m_start.container() || !m_end.container())
1722         return;
1723
1724     Node* startContainer = m_start.container();
1725     Node* endContainer = m_end.container();
1726     int startOffset = m_start.offset();
1727     int endOffset = m_end.offset();
1728
1729     Vector<SelectionRect> newRects;
1730     Node* stopNode = pastLastNode();
1731     bool hasFlippedWritingMode = startContainer->renderer() && startContainer->renderer()->style().isFlippedBlocksWritingMode();
1732     bool containsDifferentWritingModes = false;
1733     for (Node* node = firstNode(); node && node != stopNode; node = NodeTraversal::next(node)) {
1734         RenderObject* renderer = node->renderer();
1735         // Only ask leaf render objects for their line box rects.
1736         if (renderer && !renderer->firstChildSlow() && renderer->style().userSelect() != SELECT_NONE) {
1737             bool isStartNode = renderer->node() == startContainer;
1738             bool isEndNode = renderer->node() == endContainer;
1739             if (hasFlippedWritingMode != renderer->style().isFlippedBlocksWritingMode())
1740                 containsDifferentWritingModes = true;
1741             // FIXME: Sending 0 for the startOffset is a weird way of telling the renderer that the selection
1742             // doesn't start inside it, since we'll also send 0 if the selection *does* start in it, at offset 0.
1743             //
1744             // FIXME: Selection endpoints aren't always inside leaves, and we only build SelectionRects for leaves,
1745             // so we can't accurately determine which SelectionRects contain the selection start and end using
1746             // only the offsets of the start and end. We need to pass the whole Range.
1747             int beginSelectionOffset = isStartNode ? startOffset : 0;
1748             int endSelectionOffset = isEndNode ? endOffset : std::numeric_limits<int>::max();
1749             renderer->collectSelectionRects(newRects, beginSelectionOffset, endSelectionOffset);
1750             size_t numberOfNewRects = newRects.size();
1751             for (size_t i = 0; i < numberOfNewRects; ++i) {
1752                 SelectionRect& selectionRect = newRects[i];
1753                 if (selectionRect.containsStart() && !isStartNode)
1754                     selectionRect.setContainsStart(false);
1755                 if (selectionRect.containsEnd() && !isEndNode)
1756                     selectionRect.setContainsEnd(false);
1757                 if (selectionRect.logicalWidth() || selectionRect.logicalHeight())
1758                     rects.append(newRects[i]);
1759             }
1760             newRects.shrink(0);
1761         }
1762     }
1763
1764     // The range could span over nodes with different writing modes.
1765     // If this is the case, we use the writing mode of the common ancestor.
1766     if (containsDifferentWritingModes) {
1767         if (Node* ancestor = commonAncestorContainer(startContainer, endContainer))
1768             hasFlippedWritingMode = ancestor->renderer()->style().isFlippedBlocksWritingMode();
1769     }
1770
1771     const size_t numberOfRects = rects.size();
1772
1773     // If the selection ends in a BR, then add the line break bit to the last
1774     // rect we have. This will cause its selection rect to extend to the
1775     // end of the line.
1776     if (stopNode && stopNode->hasTagName(HTMLNames::brTag) && numberOfRects) {
1777         // Only set the line break bit if the end of the range actually
1778         // extends all the way to include the <br>. VisiblePosition helps to
1779         // figure this out.
1780         VisiblePosition endPosition(createLegacyEditingPosition(endContainer, endOffset), VP_DEFAULT_AFFINITY);
1781         VisiblePosition brPosition(createLegacyEditingPosition(stopNode, 0), VP_DEFAULT_AFFINITY);
1782         if (endPosition == brPosition)
1783             rects.last().setIsLineBreak(true);    
1784     }
1785
1786     int lineTop = std::numeric_limits<int>::max();
1787     int lineBottom = std::numeric_limits<int>::min();
1788     int lastLineTop = lineTop;
1789     int lastLineBottom = lineBottom;
1790     int lineNumber = 0;
1791
1792     for (size_t i = 0; i < numberOfRects; ++i) {
1793         int currentRectTop = rects[i].logicalTop();
1794         int currentRectBottom = currentRectTop + rects[i].logicalHeight();
1795
1796         // We don't want to count the ruby text as a separate line.
1797         if (intervalsSufficientlyOverlap(currentRectTop, currentRectBottom, lineTop, lineBottom) || (i && rects[i].isRubyText())) {
1798             // Grow the current line bounds.
1799             lineTop = std::min(lineTop, currentRectTop);
1800             lineBottom = std::max(lineBottom, currentRectBottom);
1801             // Avoid overlap with the previous line.
1802             if (!hasFlippedWritingMode)
1803                 lineTop = std::max(lastLineBottom, lineTop);
1804             else
1805                 lineBottom = std::min(lastLineTop, lineBottom);
1806         } else {
1807             adjustLineHeightOfSelectionRects(rects, i, lineNumber, lineTop, lineBottom - lineTop);
1808             if (!hasFlippedWritingMode) {
1809                 lastLineTop = lineTop;
1810                 if (currentRectBottom >= lastLineTop) {
1811                     lastLineBottom = lineBottom;
1812                     lineTop = lastLineBottom;
1813                 } else {
1814                     lineTop = currentRectTop;
1815                     lastLineBottom = std::numeric_limits<int>::min();
1816                 }
1817                 lineBottom = currentRectBottom;
1818             } else {
1819                 lastLineBottom = lineBottom;
1820                 if (currentRectTop <= lastLineBottom && i && rects[i].pageNumber() == rects[i - 1].pageNumber()) {
1821                     lastLineTop = lineTop;
1822                     lineBottom = lastLineTop;
1823                 } else {
1824                     lastLineTop = std::numeric_limits<int>::max();
1825                     lineBottom = currentRectBottom;
1826                 }
1827                 lineTop = currentRectTop;
1828             }
1829             ++lineNumber;
1830         }
1831     }
1832
1833     // Adjust line height.
1834     adjustLineHeightOfSelectionRects(rects, numberOfRects, lineNumber, lineTop, lineBottom - lineTop);
1835
1836     // Sort the rectangles and make sure there are no gaps. The rectangles could be unsorted when
1837     // there is ruby text and we could have gaps on the line when adjacent elements on the line
1838     // have a different orientation.
1839     size_t firstRectWithCurrentLineNumber = 0;
1840     for (size_t currentRect = 1; currentRect < numberOfRects; ++currentRect) {
1841         if (rects[currentRect].lineNumber() != rects[currentRect - 1].lineNumber()) {
1842             firstRectWithCurrentLineNumber = currentRect;
1843             continue;
1844         }
1845         if (rects[currentRect].logicalLeft() >= rects[currentRect - 1].logicalLeft())
1846             continue;
1847
1848         SelectionRect selectionRect = rects[currentRect];
1849         size_t i;
1850         for (i = currentRect; i > firstRectWithCurrentLineNumber && selectionRect.logicalLeft() < rects[i - 1].logicalLeft(); --i)
1851             rects[i] = rects[i - 1];
1852         rects[i] = selectionRect;
1853     }
1854
1855     for (size_t j = 1; j < numberOfRects; ++j) {
1856         if (rects[j].lineNumber() != rects[j - 1].lineNumber())
1857             continue;
1858         SelectionRect& previousRect = rects[j - 1];
1859         bool previousRectMayNotReachRightEdge = (previousRect.direction() == LTR && previousRect.containsEnd()) || (previousRect.direction() == RTL && previousRect.containsStart());
1860         if (previousRectMayNotReachRightEdge)
1861             continue;
1862         int adjustedWidth = rects[j].logicalLeft() - previousRect.logicalLeft();
1863         if (adjustedWidth > previousRect.logicalWidth())
1864             previousRect.setLogicalWidth(adjustedWidth);
1865     }
1866
1867     int maxLineNumber = lineNumber;
1868
1869     // Extend rects out to edges as needed.
1870     for (size_t i = 0; i < numberOfRects; ++i) {
1871         SelectionRect& selectionRect = rects[i];
1872         if (!selectionRect.isLineBreak() && selectionRect.lineNumber() >= maxLineNumber)
1873             continue;
1874         if (selectionRect.direction() == RTL && selectionRect.isFirstOnLine()) {
1875             selectionRect.setLogicalWidth(selectionRect.logicalWidth() + selectionRect.logicalLeft() - selectionRect.minX());
1876             selectionRect.setLogicalLeft(selectionRect.minX());
1877         } else if (selectionRect.direction() == LTR && selectionRect.isLastOnLine())
1878             selectionRect.setLogicalWidth(selectionRect.maxX() - selectionRect.logicalLeft());
1879     }
1880
1881     // Union all the rectangles on interior lines (i.e. not first or last).
1882     // On first and last lines, just avoid having overlaps by merging intersecting rectangles.
1883     Vector<SelectionRect> unionedRects;
1884     IntRect interiorUnionRect;
1885     for (size_t i = 0; i < numberOfRects; ++i) {
1886         SelectionRect& currentRect = rects[i];
1887         if (currentRect.lineNumber() == 1) {
1888             ASSERT(interiorUnionRect.isEmpty());
1889             if (!unionedRects.isEmpty()) {
1890                 SelectionRect& previousRect = unionedRects.last();
1891                 if (previousRect.rect().intersects(currentRect.rect())) {
1892                     previousRect = coalesceSelectionRects(currentRect, previousRect);
1893                     continue;
1894                 }
1895             }
1896             // Couldn't merge with previous rect, so just appending.
1897             unionedRects.append(currentRect);
1898         } else if (currentRect.lineNumber() < maxLineNumber) {
1899             if (interiorUnionRect.isEmpty()) {
1900                 // Start collecting interior rects.
1901                 interiorUnionRect = currentRect.rect();         
1902             } else if (interiorUnionRect.intersects(currentRect.rect())
1903                 || interiorUnionRect.maxX() == currentRect.rect().x()
1904                 || interiorUnionRect.maxY() == currentRect.rect().y()
1905                 || interiorUnionRect.x() == currentRect.rect().maxX()
1906                 || interiorUnionRect.y() == currentRect.rect().maxY()) {
1907                 // Only union the lines that are attached.
1908                 // For iBooks, the interior lines may cross multiple horizontal pages.
1909                 interiorUnionRect.unite(currentRect.rect());
1910             } else {
1911                 unionedRects.append(SelectionRect(interiorUnionRect, currentRect.isHorizontal(), currentRect.pageNumber()));
1912                 interiorUnionRect = currentRect.rect();
1913             }
1914         } else {
1915             // Processing last line.
1916             if (!interiorUnionRect.isEmpty()) {
1917                 unionedRects.append(SelectionRect(interiorUnionRect, currentRect.isHorizontal(), currentRect.pageNumber()));
1918                 interiorUnionRect = IntRect();
1919             }
1920
1921             ASSERT(!unionedRects.isEmpty());
1922             SelectionRect& previousRect = unionedRects.last();
1923             if (previousRect.logicalTop() == currentRect.logicalTop() && previousRect.rect().intersects(currentRect.rect())) {
1924                 // previousRect is also on the last line, and intersects the current one.
1925                 previousRect = coalesceSelectionRects(currentRect, previousRect);
1926                 continue;
1927             }
1928             // Couldn't merge with previous rect, so just appending.
1929             unionedRects.append(currentRect);
1930         }
1931     }
1932
1933     rects.swap(unionedRects);
1934 }
1935 #endif
1936
1937 #ifndef NDEBUG
1938 void Range::formatForDebugger(char* buffer, unsigned length) const
1939 {
1940     StringBuilder result;
1941     String s;
1942
1943     if (!m_start.container() || !m_end.container())
1944         result.appendLiteral("<empty>");
1945     else {
1946         const int FormatBufferSize = 1024;
1947         char s[FormatBufferSize];
1948         result.appendLiteral("from offset ");
1949         result.appendNumber(m_start.offset());
1950         result.appendLiteral(" of ");
1951         m_start.container()->formatForDebugger(s, FormatBufferSize);
1952         result.append(s);
1953         result.appendLiteral(" to offset ");
1954         result.appendNumber(m_end.offset());
1955         result.appendLiteral(" of ");
1956         m_end.container()->formatForDebugger(s, FormatBufferSize);
1957         result.append(s);
1958     }
1959
1960     strncpy(buffer, result.toString().utf8().data(), length - 1);
1961 }
1962 #endif
1963
1964 bool Range::contains(const Range& other) const
1965 {
1966     if (commonAncestorContainer(ASSERT_NO_EXCEPTION)->ownerDocument() != other.commonAncestorContainer(ASSERT_NO_EXCEPTION)->ownerDocument())
1967         return false;
1968
1969     short startToStart = compareBoundaryPoints(Range::START_TO_START, &other, ASSERT_NO_EXCEPTION);
1970     if (startToStart > 0)
1971         return false;
1972
1973     short endToEnd = compareBoundaryPoints(Range::END_TO_END, &other, ASSERT_NO_EXCEPTION);
1974     return endToEnd >= 0;
1975 }
1976
1977 bool areRangesEqual(const Range* a, const Range* b)
1978 {
1979     if (a == b)
1980         return true;
1981     if (!a || !b)
1982         return false;
1983     return a->startPosition() == b->startPosition() && a->endPosition() == b->endPosition();
1984 }
1985
1986 bool rangesOverlap(const Range* a, const Range* b)
1987 {
1988     if (!a || !b)
1989         return false;
1990
1991     if (a == b)
1992         return true;
1993
1994     if (a->commonAncestorContainer(ASSERT_NO_EXCEPTION)->ownerDocument() != b->commonAncestorContainer(ASSERT_NO_EXCEPTION)->ownerDocument())
1995         return false;
1996
1997     short startToStart = a->compareBoundaryPoints(Range::START_TO_START, b, ASSERT_NO_EXCEPTION);
1998     short endToEnd = a->compareBoundaryPoints(Range::END_TO_END, b, ASSERT_NO_EXCEPTION);
1999
2000     // First range contains the second range.
2001     if (startToStart <= 0 && endToEnd >= 0)
2002         return true;
2003
2004     // End of first range is inside second range.
2005     if (a->compareBoundaryPoints(Range::START_TO_END, b, ASSERT_NO_EXCEPTION) >= 0 && endToEnd <= 0)
2006         return true;
2007
2008     // Start of first range is inside second range.
2009     if (startToStart >= 0 && a->compareBoundaryPoints(Range::END_TO_START, b, ASSERT_NO_EXCEPTION) <= 0)
2010         return true;
2011
2012     return false;
2013 }
2014
2015 PassRefPtr<Range> rangeOfContents(Node& node)
2016 {
2017     RefPtr<Range> range = Range::create(node.document());
2018     int exception = 0;
2019     range->selectNodeContents(&node, exception);
2020     return range.release();
2021 }
2022
2023 static inline void boundaryNodeChildrenChanged(RangeBoundaryPoint& boundary, ContainerNode& container)
2024 {
2025     if (!boundary.childBefore())
2026         return;
2027     if (boundary.container() != &container)
2028         return;
2029     boundary.invalidateOffset();
2030 }
2031
2032 void Range::nodeChildrenChanged(ContainerNode& container)
2033 {
2034     ASSERT(&container.document() == &ownerDocument());
2035     boundaryNodeChildrenChanged(m_start, container);
2036     boundaryNodeChildrenChanged(m_end, container);
2037 }
2038
2039 static inline void boundaryNodeChildrenWillBeRemoved(RangeBoundaryPoint& boundary, ContainerNode& container)
2040 {
2041     for (Node* nodeToBeRemoved = container.firstChild(); nodeToBeRemoved; nodeToBeRemoved = nodeToBeRemoved->nextSibling()) {
2042         if (boundary.childBefore() == nodeToBeRemoved) {
2043             boundary.setToStartOfNode(&container);
2044             return;
2045         }
2046
2047         for (Node* n = boundary.container(); n; n = n->parentNode()) {
2048             if (n == nodeToBeRemoved) {
2049                 boundary.setToStartOfNode(&container);
2050                 return;
2051             }
2052         }
2053     }
2054 }
2055
2056 void Range::nodeChildrenWillBeRemoved(ContainerNode& container)
2057 {
2058     ASSERT(&container.document() == &ownerDocument());
2059     boundaryNodeChildrenWillBeRemoved(m_start, container);
2060     boundaryNodeChildrenWillBeRemoved(m_end, container);
2061 }
2062
2063 static inline void boundaryNodeWillBeRemoved(RangeBoundaryPoint& boundary, Node* nodeToBeRemoved)
2064 {
2065     if (boundary.childBefore() == nodeToBeRemoved) {
2066         boundary.childBeforeWillBeRemoved();
2067         return;
2068     }
2069
2070     for (Node* n = boundary.container(); n; n = n->parentNode()) {
2071         if (n == nodeToBeRemoved) {
2072             boundary.setToBeforeChild(nodeToBeRemoved);
2073             return;
2074         }
2075     }
2076 }
2077
2078 void Range::nodeWillBeRemoved(Node* node)
2079 {
2080     ASSERT(node);
2081     ASSERT(&node->document() == &ownerDocument());
2082     ASSERT(node != &ownerDocument());
2083     ASSERT(node->parentNode());
2084     boundaryNodeWillBeRemoved(m_start, node);
2085     boundaryNodeWillBeRemoved(m_end, node);
2086 }
2087
2088 static inline void boundaryTextInserted(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
2089 {
2090     if (boundary.container() != text)
2091         return;
2092     unsigned boundaryOffset = boundary.offset();
2093     if (offset >= boundaryOffset)
2094         return;
2095     boundary.setOffset(boundaryOffset + length);
2096 }
2097
2098 void Range::textInserted(Node* text, unsigned offset, unsigned length)
2099 {
2100     ASSERT(text);
2101     ASSERT(&text->document() == &ownerDocument());
2102     boundaryTextInserted(m_start, text, offset, length);
2103     boundaryTextInserted(m_end, text, offset, length);
2104 }
2105
2106 static inline void boundaryTextRemoved(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
2107 {
2108     if (boundary.container() != text)
2109         return;
2110     unsigned boundaryOffset = boundary.offset();
2111     if (offset >= boundaryOffset)
2112         return;
2113     if (offset + length >= boundaryOffset)
2114         boundary.setOffset(offset);
2115     else
2116         boundary.setOffset(boundaryOffset - length);
2117 }
2118
2119 void Range::textRemoved(Node* text, unsigned offset, unsigned length)
2120 {
2121     ASSERT(text);
2122     ASSERT(&text->document() == &ownerDocument());
2123     boundaryTextRemoved(m_start, text, offset, length);
2124     boundaryTextRemoved(m_end, text, offset, length);
2125 }
2126
2127 static inline void boundaryTextNodesMerged(RangeBoundaryPoint& boundary, NodeWithIndex& oldNode, unsigned offset)
2128 {
2129     if (boundary.container() == oldNode.node())
2130         boundary.set(oldNode.node()->previousSibling(), boundary.offset() + offset, 0);
2131     else if (boundary.container() == oldNode.node()->parentNode() && boundary.offset() == oldNode.index())
2132         boundary.set(oldNode.node()->previousSibling(), offset, 0);
2133 }
2134
2135 void Range::textNodesMerged(NodeWithIndex& oldNode, unsigned offset)
2136 {
2137     ASSERT(oldNode.node());
2138     ASSERT(&oldNode.node()->document() == &ownerDocument());
2139     ASSERT(oldNode.node()->parentNode());
2140     ASSERT(oldNode.node()->isTextNode());
2141     ASSERT(oldNode.node()->previousSibling());
2142     ASSERT(oldNode.node()->previousSibling()->isTextNode());
2143     boundaryTextNodesMerged(m_start, oldNode, offset);
2144     boundaryTextNodesMerged(m_end, oldNode, offset);
2145 }
2146
2147 static inline void boundaryTextNodesSplit(RangeBoundaryPoint& boundary, Text* oldNode)
2148 {
2149     if (boundary.container() != oldNode)
2150         return;
2151     unsigned boundaryOffset = boundary.offset();
2152     if (boundaryOffset <= oldNode->length())
2153         return;
2154     boundary.set(oldNode->nextSibling(), boundaryOffset - oldNode->length(), 0);
2155 }
2156
2157 void Range::textNodeSplit(Text* oldNode)
2158 {
2159     ASSERT(oldNode);
2160     ASSERT(&oldNode->document() == &ownerDocument());
2161     ASSERT(oldNode->parentNode());
2162     ASSERT(oldNode->isTextNode());
2163     ASSERT(oldNode->nextSibling());
2164     ASSERT(oldNode->nextSibling()->isTextNode());
2165     boundaryTextNodesSplit(m_start, oldNode);
2166     boundaryTextNodesSplit(m_end, oldNode);
2167 }
2168
2169 void Range::expand(const String& unit, ExceptionCode& ec)
2170 {
2171     VisiblePosition start(startPosition());
2172     VisiblePosition end(endPosition());
2173     if (unit == "word") {
2174         start = startOfWord(start);
2175         end = endOfWord(end);
2176     } else if (unit == "sentence") {
2177         start = startOfSentence(start);
2178         end = endOfSentence(end);
2179     } else if (unit == "block") {
2180         start = startOfParagraph(start);
2181         end = endOfParagraph(end);
2182     } else if (unit == "document") {
2183         start = startOfDocument(start);
2184         end = endOfDocument(end);
2185     } else
2186         return;
2187     setStart(start.deepEquivalent().containerNode(), start.deepEquivalent().computeOffsetInContainerNode(), ec);
2188     setEnd(end.deepEquivalent().containerNode(), end.deepEquivalent().computeOffsetInContainerNode(), ec);
2189 }
2190
2191 PassRefPtr<ClientRectList> Range::getClientRects() const
2192 {
2193     if (!m_start.container())
2194         return ClientRectList::create();
2195
2196     ownerDocument().updateLayoutIgnorePendingStylesheets();
2197
2198     Vector<FloatQuad> quads;
2199     getBorderAndTextQuads(quads);
2200
2201     return ClientRectList::create(quads);
2202 }
2203
2204 PassRefPtr<ClientRect> Range::getBoundingClientRect() const
2205 {
2206     return ClientRect::create(boundingRect());
2207 }
2208
2209 void Range::getBorderAndTextQuads(Vector<FloatQuad>& quads) const
2210 {
2211     Node* startContainer = m_start.container();
2212     Node* endContainer = m_end.container();
2213     Node* stopNode = pastLastNode();
2214
2215     HashSet<Node*> selectedElementsSet;
2216     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
2217         if (node->isElementNode())
2218             selectedElementsSet.add(node);
2219     }
2220
2221     // Don't include elements that are only partially selected.
2222     Node* lastNode = m_end.childBefore() ? m_end.childBefore() : endContainer;
2223     for (Node* parent = lastNode->parentNode(); parent; parent = parent->parentNode())
2224         selectedElementsSet.remove(parent);
2225
2226     for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(node)) {
2227         if (is<Element>(*node) && selectedElementsSet.contains(node) && !selectedElementsSet.contains(node->parentNode())) {
2228             if (RenderBoxModelObject* renderBoxModelObject = downcast<Element>(*node).renderBoxModelObject()) {
2229                 Vector<FloatQuad> elementQuads;
2230                 renderBoxModelObject->absoluteQuads(elementQuads);
2231                 ownerDocument().adjustFloatQuadsForScrollAndAbsoluteZoomAndFrameScale(elementQuads, renderBoxModelObject->style());
2232
2233                 quads.appendVector(elementQuads);
2234             }
2235         } else if (is<Text>(*node)) {
2236             if (RenderText* renderText = downcast<Text>(*node).renderer()) {
2237                 int startOffset = (node == startContainer) ? m_start.offset() : 0;
2238                 int endOffset = (node == endContainer) ? m_end.offset() : INT_MAX;
2239                 
2240                 auto textQuads = renderText->absoluteQuadsForRange(startOffset, endOffset);
2241                 ownerDocument().adjustFloatQuadsForScrollAndAbsoluteZoomAndFrameScale(textQuads, renderText->style());
2242
2243                 quads.appendVector(textQuads);
2244             }
2245         }
2246     }
2247 }
2248
2249 FloatRect Range::boundingRect() const
2250 {
2251     if (!m_start.container())
2252         return FloatRect();
2253
2254     ownerDocument().updateLayoutIgnorePendingStylesheets();
2255
2256     Vector<FloatQuad> quads;
2257     getBorderAndTextQuads(quads);
2258     if (quads.isEmpty())
2259         return FloatRect();
2260
2261     FloatRect result;
2262     for (size_t i = 0; i < quads.size(); ++i)
2263         result.unite(quads[i].boundingBox());
2264
2265     return result;
2266 }
2267
2268 } // namespace WebCore
2269
2270 #ifndef NDEBUG
2271
2272 void showTree(const WebCore::Range* range)
2273 {
2274     if (range && range->boundaryPointsValid()) {
2275         range->startContainer()->showTreeAndMark(range->startContainer(), "S", range->endContainer(), "E");
2276         fprintf(stderr, "start offset: %d, end offset: %d\n", range->startOffset(), range->endOffset());
2277     }
2278 }
2279
2280 #endif