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