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