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