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