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