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