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