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