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