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 Apple Inc. All rights reserved.
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Library General Public
10  * License as published by the Free Software Foundation; either
11  * version 2 of the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  * Library General Public License for more details.
17  *
18  * You should have received a copy of the GNU Library General Public License
19  * along with this library; see the file COPYING.LIB.  If not, write to
20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21  * Boston, MA 02110-1301, USA.
22  */
23 
24 #include "config.h"
25 #include "Range.h"
26 #include "RangeException.h"
27 
28 #include "ClientRect.h"
29 #include "ClientRectList.h"
30 #include "DocumentFragment.h"
31 #include "FrameView.h"
32 #include "HTMLElement.h"
33 #include "NodeWithIndex.h"
34 #include "ProcessingInstruction.h"
35 #include "Text.h"
36 #include "TextIterator.h"
37 #include "VisiblePosition.h"
38 #include "htmlediting.h"
39 #include "markup.h"
40 #include "visible_units.h"
41 #include <stdio.h>
42 #include <wtf/text/CString.h>
43 #include <wtf/RefCountedLeakCounter.h>
44 #include <wtf/Vector.h>
45 
46 namespace WebCore {
47 
48 using namespace std;
49 
50 #ifndef NDEBUG
51 static WTF::RefCountedLeakCounter rangeCounter("Range");
52 #endif
53 
54 typedef Vector<RefPtr<Node> > NodeVector;
55 
Range(PassRefPtr<Document> ownerDocument)56 inline Range::Range(PassRefPtr<Document> ownerDocument)
57     : m_ownerDocument(ownerDocument)
58     , m_start(m_ownerDocument)
59     , m_end(m_ownerDocument)
60 {
61 #ifndef NDEBUG
62     rangeCounter.increment();
63 #endif
64 
65     m_ownerDocument->attachRange(this);
66 }
67 
create(PassRefPtr<Document> ownerDocument)68 PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument)
69 {
70     return adoptRef(new Range(ownerDocument));
71 }
72 
Range(PassRefPtr<Document> ownerDocument,PassRefPtr<Node> startContainer,int startOffset,PassRefPtr<Node> endContainer,int endOffset)73 inline Range::Range(PassRefPtr<Document> ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)
74     : m_ownerDocument(ownerDocument)
75     , m_start(m_ownerDocument)
76     , m_end(m_ownerDocument)
77 {
78 #ifndef NDEBUG
79     rangeCounter.increment();
80 #endif
81 
82     m_ownerDocument->attachRange(this);
83 
84     // Simply setting the containers and offsets directly would not do any of the checking
85     // that setStart and setEnd do, so we call those functions.
86     ExceptionCode ec = 0;
87     setStart(startContainer, startOffset, ec);
88     ASSERT(!ec);
89     setEnd(endContainer, endOffset, ec);
90     ASSERT(!ec);
91 }
92 
create(PassRefPtr<Document> ownerDocument,PassRefPtr<Node> startContainer,int startOffset,PassRefPtr<Node> endContainer,int endOffset)93 PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)
94 {
95     return adoptRef(new Range(ownerDocument, startContainer, startOffset, endContainer, endOffset));
96 }
97 
create(PassRefPtr<Document> ownerDocument,const Position & start,const Position & end)98 PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument, const Position& start, const Position& end)
99 {
100     return adoptRef(new Range(ownerDocument, start.containerNode(), start.computeOffsetInContainerNode(), end.containerNode(), end.computeOffsetInContainerNode()));
101 }
102 
~Range()103 Range::~Range()
104 {
105     // Always detach (even if we've already detached) to fix https://bugs.webkit.org/show_bug.cgi?id=26044
106     m_ownerDocument->detachRange(this);
107 
108 #ifndef NDEBUG
109     rangeCounter.decrement();
110 #endif
111 }
112 
setDocument(Document * document)113 void Range::setDocument(Document* document)
114 {
115     ASSERT(m_ownerDocument != document);
116     if (m_ownerDocument)
117         m_ownerDocument->detachRange(this);
118     m_ownerDocument = document;
119     m_start.setToStartOfNode(document);
120     m_end.setToStartOfNode(document);
121     m_ownerDocument->attachRange(this);
122 }
123 
startContainer(ExceptionCode & ec) const124 Node* Range::startContainer(ExceptionCode& ec) const
125 {
126     if (!m_start.container()) {
127         ec = INVALID_STATE_ERR;
128         return 0;
129     }
130 
131     return m_start.container();
132 }
133 
startOffset(ExceptionCode & ec) const134 int Range::startOffset(ExceptionCode& ec) const
135 {
136     if (!m_start.container()) {
137         ec = INVALID_STATE_ERR;
138         return 0;
139     }
140 
141     return m_start.offset();
142 }
143 
endContainer(ExceptionCode & ec) const144 Node* Range::endContainer(ExceptionCode& ec) const
145 {
146     if (!m_start.container()) {
147         ec = INVALID_STATE_ERR;
148         return 0;
149     }
150 
151     return m_end.container();
152 }
153 
endOffset(ExceptionCode & ec) const154 int Range::endOffset(ExceptionCode& ec) const
155 {
156     if (!m_start.container()) {
157         ec = INVALID_STATE_ERR;
158         return 0;
159     }
160 
161     return m_end.offset();
162 }
163 
commonAncestorContainer(ExceptionCode & ec) const164 Node* Range::commonAncestorContainer(ExceptionCode& ec) const
165 {
166     if (!m_start.container()) {
167         ec = INVALID_STATE_ERR;
168         return 0;
169     }
170 
171     return commonAncestorContainer(m_start.container(), m_end.container());
172 }
173 
commonAncestorContainer(Node * containerA,Node * containerB)174 Node* Range::commonAncestorContainer(Node* containerA, Node* containerB)
175 {
176     for (Node* parentA = containerA; parentA; parentA = parentA->parentNode()) {
177         for (Node* parentB = containerB; parentB; parentB = parentB->parentNode()) {
178             if (parentA == parentB)
179                 return parentA;
180         }
181     }
182     return 0;
183 }
184 
collapsed(ExceptionCode & ec) const185 bool Range::collapsed(ExceptionCode& ec) const
186 {
187     if (!m_start.container()) {
188         ec = INVALID_STATE_ERR;
189         return 0;
190     }
191 
192     return m_start == m_end;
193 }
194 
setStart(PassRefPtr<Node> refNode,int offset,ExceptionCode & ec)195 void Range::setStart(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
196 {
197     if (!m_start.container()) {
198         ec = INVALID_STATE_ERR;
199         return;
200     }
201 
202     if (!refNode) {
203         ec = NOT_FOUND_ERR;
204         return;
205     }
206 
207     if (refNode->document() != m_ownerDocument) {
208         ec = WRONG_DOCUMENT_ERR;
209         return;
210     }
211 
212     ec = 0;
213     Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);
214     if (ec)
215         return;
216 
217     m_start.set(refNode, offset, childNode);
218 
219     // check if different root container
220     Node* endRootContainer = m_end.container();
221     while (endRootContainer->parentNode())
222         endRootContainer = endRootContainer->parentNode();
223     Node* startRootContainer = m_start.container();
224     while (startRootContainer->parentNode())
225         startRootContainer = startRootContainer->parentNode();
226     if (startRootContainer != endRootContainer)
227         collapse(true, ec);
228     // check if new start after end
229     else if (compareBoundaryPoints(m_start, m_end, ec) > 0) {
230         ASSERT(!ec);
231         collapse(true, ec);
232     }
233 }
234 
setEnd(PassRefPtr<Node> refNode,int offset,ExceptionCode & ec)235 void Range::setEnd(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
236 {
237     if (!m_start.container()) {
238         ec = INVALID_STATE_ERR;
239         return;
240     }
241 
242     if (!refNode) {
243         ec = NOT_FOUND_ERR;
244         return;
245     }
246 
247     if (refNode->document() != m_ownerDocument) {
248         ec = WRONG_DOCUMENT_ERR;
249         return;
250     }
251 
252     ec = 0;
253     Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);
254     if (ec)
255         return;
256 
257     m_end.set(refNode, offset, childNode);
258 
259     // check if different root container
260     Node* endRootContainer = m_end.container();
261     while (endRootContainer->parentNode())
262         endRootContainer = endRootContainer->parentNode();
263     Node* startRootContainer = m_start.container();
264     while (startRootContainer->parentNode())
265         startRootContainer = startRootContainer->parentNode();
266     if (startRootContainer != endRootContainer)
267         collapse(false, ec);
268     // check if new end before start
269     if (compareBoundaryPoints(m_start, m_end, ec) > 0) {
270         ASSERT(!ec);
271         collapse(false, ec);
272     }
273 }
274 
collapse(bool toStart,ExceptionCode & ec)275 void Range::collapse(bool toStart, ExceptionCode& ec)
276 {
277     if (!m_start.container()) {
278         ec = INVALID_STATE_ERR;
279         return;
280     }
281 
282     if (toStart)
283         m_end = m_start;
284     else
285         m_start = m_end;
286 }
287 
isPointInRange(Node * refNode,int offset,ExceptionCode & ec)288 bool Range::isPointInRange(Node* refNode, int offset, ExceptionCode& ec)
289 {
290     if (!m_start.container()) {
291         ec = INVALID_STATE_ERR;
292         return false;
293     }
294 
295     if (!refNode) {
296         ec = HIERARCHY_REQUEST_ERR;
297         return false;
298     }
299 
300     if (!refNode->attached()) {
301         // Firefox doesn't throw an exception for this case; it returns false.
302         return false;
303     }
304 
305     if (refNode->document() != m_ownerDocument) {
306         ec = WRONG_DOCUMENT_ERR;
307         return false;
308     }
309 
310     ec = 0;
311     checkNodeWOffset(refNode, offset, ec);
312     if (ec)
313         return false;
314 
315     return compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset(), ec) >= 0 && !ec
316         && compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset(), ec) <= 0 && !ec;
317 }
318 
comparePoint(Node * refNode,int offset,ExceptionCode & ec) const319 short Range::comparePoint(Node* refNode, int offset, ExceptionCode& ec) const
320 {
321     // http://developer.mozilla.org/en/docs/DOM:range.comparePoint
322     // This method returns -1, 0 or 1 depending on if the point described by the
323     // refNode node and an offset within the node is before, same as, or after the range respectively.
324 
325     if (!m_start.container()) {
326         ec = INVALID_STATE_ERR;
327         return 0;
328     }
329 
330     if (!refNode) {
331         ec = HIERARCHY_REQUEST_ERR;
332         return 0;
333     }
334 
335     if (!refNode->attached() || refNode->document() != m_ownerDocument) {
336         ec = WRONG_DOCUMENT_ERR;
337         return 0;
338     }
339 
340     ec = 0;
341     checkNodeWOffset(refNode, offset, ec);
342     if (ec)
343         return 0;
344 
345     // compare to start, and point comes before
346     if (compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset(), ec) < 0)
347         return -1;
348 
349     if (ec)
350         return 0;
351 
352     // compare to end, and point comes after
353     if (compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset(), ec) > 0 && !ec)
354         return 1;
355 
356     // point is in the middle of this range, or on the boundary points
357     return 0;
358 }
359 
compareNode(Node * refNode,ExceptionCode & ec) const360 Range::CompareResults Range::compareNode(Node* refNode, ExceptionCode& ec) const
361 {
362     // http://developer.mozilla.org/en/docs/DOM:range.compareNode
363     // This method returns 0, 1, 2, or 3 based on if the node is before, after,
364     // before and after(surrounds), or inside the range, respectively
365 
366     if (!refNode) {
367         ec = NOT_FOUND_ERR;
368         return NODE_BEFORE;
369     }
370 
371     if (!m_start.container() && refNode->attached()) {
372         ec = INVALID_STATE_ERR;
373         return NODE_BEFORE;
374     }
375 
376     if (m_start.container() && !refNode->attached()) {
377         // Firefox doesn't throw an exception for this case; it returns 0.
378         return NODE_BEFORE;
379     }
380 
381     if (refNode->document() != m_ownerDocument) {
382         // Firefox doesn't throw an exception for this case; it returns 0.
383         return NODE_BEFORE;
384     }
385 
386     ContainerNode* parentNode = refNode->parentNode();
387     int nodeIndex = refNode->nodeIndex();
388 
389     if (!parentNode) {
390         // if the node is the top document we should return NODE_BEFORE_AND_AFTER
391         // but we throw to match firefox behavior
392         ec = NOT_FOUND_ERR;
393         return NODE_BEFORE;
394     }
395 
396     if (comparePoint(parentNode, nodeIndex, ec) < 0) { // starts before
397         if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range
398             return NODE_BEFORE_AND_AFTER;
399         return NODE_BEFORE; // ends before or in the range
400     } else { // starts at or after the range start
401         if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range
402             return NODE_AFTER;
403         return NODE_INSIDE; // ends inside the range
404     }
405 }
406 
compareBoundaryPoints(CompareHow how,const Range * sourceRange,ExceptionCode & ec) const407 short Range::compareBoundaryPoints(CompareHow how, const Range* sourceRange, ExceptionCode& ec) const
408 {
409     if (!m_start.container()) {
410         ec = INVALID_STATE_ERR;
411         return 0;
412     }
413 
414     if (!sourceRange) {
415         ec = NOT_FOUND_ERR;
416         return 0;
417     }
418 
419     ec = 0;
420     Node* thisCont = commonAncestorContainer(ec);
421     if (ec)
422         return 0;
423     Node* sourceCont = sourceRange->commonAncestorContainer(ec);
424     if (ec)
425         return 0;
426 
427     if (thisCont->document() != sourceCont->document()) {
428         ec = WRONG_DOCUMENT_ERR;
429         return 0;
430     }
431 
432     Node* thisTop = thisCont;
433     Node* sourceTop = sourceCont;
434     while (thisTop->parentNode())
435         thisTop = thisTop->parentNode();
436     while (sourceTop->parentNode())
437         sourceTop = sourceTop->parentNode();
438     if (thisTop != sourceTop) { // in different DocumentFragments
439         ec = WRONG_DOCUMENT_ERR;
440         return 0;
441     }
442 
443     switch (how) {
444         case START_TO_START:
445             return compareBoundaryPoints(m_start, sourceRange->m_start, ec);
446         case START_TO_END:
447             return compareBoundaryPoints(m_end, sourceRange->m_start, ec);
448         case END_TO_END:
449             return compareBoundaryPoints(m_end, sourceRange->m_end, ec);
450         case END_TO_START:
451             return compareBoundaryPoints(m_start, sourceRange->m_end, ec);
452     }
453 
454     ec = SYNTAX_ERR;
455     return 0;
456 }
457 
compareBoundaryPoints(Node * containerA,int offsetA,Node * containerB,int offsetB,ExceptionCode & ec)458 short Range::compareBoundaryPoints(Node* containerA, int offsetA, Node* containerB, int offsetB, ExceptionCode& ec)
459 {
460     ASSERT(containerA);
461     ASSERT(containerB);
462 
463     if (!containerA)
464         return -1;
465     if (!containerB)
466         return 1;
467 
468     // see DOM2 traversal & range section 2.5
469 
470     // case 1: both points have the same container
471     if (containerA == containerB) {
472         if (offsetA == offsetB)
473             return 0;           // A is equal to B
474         if (offsetA < offsetB)
475             return -1;          // A is before B
476         else
477             return 1;           // A is after B
478     }
479 
480     // case 2: node C (container B or an ancestor) is a child node of A
481     Node* c = containerB;
482     while (c && c->parentNode() != containerA)
483         c = c->parentNode();
484     if (c) {
485         int offsetC = 0;
486         Node* n = containerA->firstChild();
487         while (n != c && offsetC < offsetA) {
488             offsetC++;
489             n = n->nextSibling();
490         }
491 
492         if (offsetA <= offsetC)
493             return -1;              // A is before B
494         else
495             return 1;               // A is after B
496     }
497 
498     // case 3: node C (container A or an ancestor) is a child node of B
499     c = containerA;
500     while (c && c->parentNode() != containerB)
501         c = c->parentNode();
502     if (c) {
503         int offsetC = 0;
504         Node* n = containerB->firstChild();
505         while (n != c && offsetC < offsetB) {
506             offsetC++;
507             n = n->nextSibling();
508         }
509 
510         if (offsetC < offsetB)
511             return -1;              // A is before B
512         else
513             return 1;               // A is after B
514     }
515 
516     // case 4: containers A & B are siblings, or children of siblings
517     // ### we need to do a traversal here instead
518     Node* commonAncestor = commonAncestorContainer(containerA, containerB);
519     if (!commonAncestor) {
520         ec = WRONG_DOCUMENT_ERR;
521         return 0;
522     }
523     Node* childA = containerA;
524     while (childA && childA->parentNode() != commonAncestor)
525         childA = childA->parentNode();
526     if (!childA)
527         childA = commonAncestor;
528     Node* childB = containerB;
529     while (childB && childB->parentNode() != commonAncestor)
530         childB = childB->parentNode();
531     if (!childB)
532         childB = commonAncestor;
533 
534     if (childA == childB)
535         return 0; // A is equal to B
536 
537     Node* n = commonAncestor->firstChild();
538     while (n) {
539         if (n == childA)
540             return -1; // A is before B
541         if (n == childB)
542             return 1; // A is after B
543         n = n->nextSibling();
544     }
545 
546     // Should never reach this point.
547     ASSERT_NOT_REACHED();
548     return 0;
549 }
550 
compareBoundaryPoints(const RangeBoundaryPoint & boundaryA,const RangeBoundaryPoint & boundaryB,ExceptionCode & ec)551 short Range::compareBoundaryPoints(const RangeBoundaryPoint& boundaryA, const RangeBoundaryPoint& boundaryB, ExceptionCode& ec)
552 {
553     return compareBoundaryPoints(boundaryA.container(), boundaryA.offset(), boundaryB.container(), boundaryB.offset(), ec);
554 }
555 
boundaryPointsValid() const556 bool Range::boundaryPointsValid() const
557 {
558     ExceptionCode ec = 0;
559     return m_start.container() && compareBoundaryPoints(m_start, m_end, ec) <= 0 && !ec;
560 }
561 
deleteContents(ExceptionCode & ec)562 void Range::deleteContents(ExceptionCode& ec)
563 {
564     checkDeleteExtract(ec);
565     if (ec)
566         return;
567 
568     processContents(DELETE_CONTENTS, ec);
569 }
570 
intersectsNode(Node * refNode,ExceptionCode & ec)571 bool Range::intersectsNode(Node* refNode, ExceptionCode& ec)
572 {
573     // http://developer.mozilla.org/en/docs/DOM:range.intersectsNode
574     // Returns a bool if the node intersects the range.
575 
576     if (!refNode) {
577         ec = NOT_FOUND_ERR;
578         return false;
579     }
580 
581     if ((!m_start.container() && refNode->attached())
582             || (m_start.container() && !refNode->attached())
583             || refNode->document() != m_ownerDocument) {
584         // Firefox doesn't throw an exception for these cases; it returns false.
585         return false;
586     }
587 
588     ContainerNode* parentNode = refNode->parentNode();
589     int nodeIndex = refNode->nodeIndex();
590 
591     if (!parentNode) {
592         // if the node is the top document we should return NODE_BEFORE_AND_AFTER
593         // but we throw to match firefox behavior
594         ec = NOT_FOUND_ERR;
595         return false;
596     }
597 
598     if (comparePoint(parentNode, nodeIndex, ec) < 0 && // starts before start
599         comparePoint(parentNode, nodeIndex + 1, ec) < 0) { // ends before start
600         return false;
601     } else if (comparePoint(parentNode, nodeIndex, ec) > 0 && // starts after end
602                comparePoint(parentNode, nodeIndex + 1, ec) > 0) { // ends after end
603         return false;
604     }
605 
606     return true; // all other cases
607 }
608 
highestAncestorUnderCommonRoot(Node * node,Node * commonRoot)609 static inline Node* highestAncestorUnderCommonRoot(Node* node, Node* commonRoot)
610 {
611     if (node == commonRoot)
612         return 0;
613 
614     ASSERT(commonRoot->contains(node));
615 
616     while (node->parentNode() != commonRoot)
617         node = node->parentNode();
618 
619     return node;
620 }
621 
childOfCommonRootBeforeOffset(Node * container,unsigned offset,Node * commonRoot)622 static inline Node* childOfCommonRootBeforeOffset(Node* container, unsigned offset, Node* commonRoot)
623 {
624     ASSERT(container);
625     ASSERT(commonRoot);
626 
627     if (!commonRoot->contains(container))
628         return 0;
629 
630     if (container == commonRoot) {
631         container = container->firstChild();
632         for (unsigned i = 0; container && i < offset; i++)
633             container = container->nextSibling();
634     } else {
635         while (container->parentNode() != commonRoot)
636             container = container->parentNode();
637     }
638 
639     return container;
640 }
641 
lengthOfContentsInNode(Node * node)642 static inline unsigned lengthOfContentsInNode(Node* node)
643 {
644     // This switch statement must be consistent with that of Range::processContentsBetweenOffsets.
645     switch (node->nodeType()) {
646     case Node::TEXT_NODE:
647     case Node::CDATA_SECTION_NODE:
648     case Node::COMMENT_NODE:
649         return static_cast<CharacterData*>(node)->length();
650     case Node::PROCESSING_INSTRUCTION_NODE:
651         return static_cast<ProcessingInstruction*>(node)->data().length();
652     case Node::ELEMENT_NODE:
653     case Node::ATTRIBUTE_NODE:
654     case Node::ENTITY_REFERENCE_NODE:
655     case Node::ENTITY_NODE:
656     case Node::DOCUMENT_NODE:
657     case Node::DOCUMENT_TYPE_NODE:
658     case Node::DOCUMENT_FRAGMENT_NODE:
659     case Node::NOTATION_NODE:
660     case Node::XPATH_NAMESPACE_NODE:
661     case Node::SHADOW_ROOT_NODE:
662         return node->childNodeCount();
663     }
664     ASSERT_NOT_REACHED();
665     return 0;
666 }
667 
processContents(ActionType action,ExceptionCode & ec)668 PassRefPtr<DocumentFragment> Range::processContents(ActionType action, ExceptionCode& ec)
669 {
670     RefPtr<DocumentFragment> fragment;
671     if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)
672         fragment = DocumentFragment::create(m_ownerDocument.get());
673 
674     ec = 0;
675     if (collapsed(ec))
676         return fragment.release();
677     if (ec)
678         return 0;
679 
680     RefPtr<Node> commonRoot = commonAncestorContainer(ec);
681     if (ec)
682         return 0;
683     ASSERT(commonRoot);
684 
685     if (m_start.container() == m_end.container()) {
686         processContentsBetweenOffsets(action, fragment, m_start.container(), m_start.offset(), m_end.offset(), ec);
687         return fragment;
688     }
689 
690     // what is the highest node that partially selects the start / end of the range?
691     RefPtr<Node> partialStart = highestAncestorUnderCommonRoot(m_start.container(), commonRoot.get());
692     RefPtr<Node> partialEnd = highestAncestorUnderCommonRoot(m_end.container(), commonRoot.get());
693 
694     // Start and end containers are different.
695     // There are three possibilities here:
696     // 1. Start container == commonRoot (End container must be a descendant)
697     // 2. End container == commonRoot (Start container must be a descendant)
698     // 3. Neither is commonRoot, they are both descendants
699     //
700     // In case 3, we grab everything after the start (up until a direct child
701     // of commonRoot) into leftContents, and everything before the end (up until
702     // a direct child of commonRoot) into rightContents. Then we process all
703     // commonRoot children between leftContents and rightContents
704     //
705     // In case 1 or 2, we skip either processing of leftContents or rightContents,
706     // in which case the last lot of nodes either goes from the first or last
707     // child of commonRoot.
708     //
709     // These are deleted, cloned, or extracted (i.e. both) depending on action.
710 
711     // Note that we are verifying that our common root hierarchy is still intact
712     // after any DOM mutation event, at various stages below. See webkit bug 60350.
713 
714     RefPtr<Node> leftContents;
715     if (m_start.container() != commonRoot && commonRoot->contains(m_start.container())) {
716         leftContents = processContentsBetweenOffsets(action, 0, m_start.container(), m_start.offset(), lengthOfContentsInNode(m_start.container()), ec);
717         leftContents = processAncestorsAndTheirSiblings(action, m_start.container(), ProcessContentsForward, leftContents, commonRoot.get(), ec);
718     }
719 
720     RefPtr<Node> rightContents;
721     if (m_end.container() != commonRoot && commonRoot->contains(m_end.container())) {
722         rightContents = processContentsBetweenOffsets(action, 0, m_end.container(), 0, m_end.offset(), ec);
723         rightContents = processAncestorsAndTheirSiblings(action, m_end.container(), ProcessContentsBackward, rightContents, commonRoot.get(), ec);
724     }
725 
726     // delete all children of commonRoot between the start and end container
727     RefPtr<Node> processStart = childOfCommonRootBeforeOffset(m_start.container(), m_start.offset(), commonRoot.get());
728     if (processStart && m_start.container() != commonRoot) // processStart contains nodes before m_start.
729         processStart = processStart->nextSibling();
730     RefPtr<Node> processEnd = childOfCommonRootBeforeOffset(m_end.container(), m_end.offset(), commonRoot.get());
731 
732     // Collapse the range, making sure that the result is not within a node that was partially selected.
733     if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
734         if (partialStart && commonRoot->contains(partialStart.get()))
735             setStart(partialStart->parentNode(), partialStart->nodeIndex() + 1, ec);
736         else if (partialEnd && commonRoot->contains(partialEnd.get()))
737             setStart(partialEnd->parentNode(), partialEnd->nodeIndex(), ec);
738         if (ec)
739             return 0;
740         m_end = m_start;
741     }
742 
743     // Now add leftContents, stuff in between, and rightContents to the fragment
744     // (or just delete the stuff in between)
745 
746     if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && leftContents)
747         fragment->appendChild(leftContents, ec);
748 
749     if (processStart) {
750         NodeVector nodes;
751         for (Node* n = processStart.get(); n && n != processEnd; n = n->nextSibling())
752             nodes.append(n);
753         processNodes(action, nodes, commonRoot, fragment, ec);
754     }
755 
756     if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && rightContents)
757         fragment->appendChild(rightContents, ec);
758 
759     return fragment.release();
760 }
761 
deleteCharacterData(PassRefPtr<CharacterData> data,unsigned startOffset,unsigned endOffset,ExceptionCode & ec)762 static inline void deleteCharacterData(PassRefPtr<CharacterData> data, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
763 {
764     if (data->length() - endOffset)
765         data->deleteData(endOffset, data->length() - endOffset, ec);
766     if (startOffset)
767         data->deleteData(0, startOffset, ec);
768 }
769 
processContentsBetweenOffsets(ActionType action,PassRefPtr<DocumentFragment> fragment,Node * container,unsigned startOffset,unsigned endOffset,ExceptionCode & ec)770 PassRefPtr<Node> Range::processContentsBetweenOffsets(ActionType action, PassRefPtr<DocumentFragment> fragment,
771     Node* container, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
772 {
773     ASSERT(container);
774     ASSERT(startOffset <= endOffset);
775 
776     // This switch statement must be consistent with that of lengthOfContentsInNode.
777     RefPtr<Node> result;
778     switch (container->nodeType()) {
779     case Node::TEXT_NODE:
780     case Node::CDATA_SECTION_NODE:
781     case Node::COMMENT_NODE:
782         ASSERT(endOffset <= static_cast<CharacterData*>(container)->length());
783         if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
784             RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(container->cloneNode(true));
785             deleteCharacterData(c, startOffset, endOffset, ec);
786             if (fragment) {
787                 result = fragment;
788                 result->appendChild(c.release(), ec);
789             } else
790                 result = c.release();
791         }
792         if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS)
793             static_cast<CharacterData*>(container)->deleteData(startOffset, endOffset - startOffset, ec);
794         break;
795     case Node::PROCESSING_INSTRUCTION_NODE:
796         ASSERT(endOffset <= static_cast<ProcessingInstruction*>(container)->data().length());
797         if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
798             RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(container->cloneNode(true));
799             c->setData(c->data().substring(startOffset, endOffset - startOffset), ec);
800             if (fragment) {
801                 result = fragment;
802                 result->appendChild(c.release(), ec);
803             } else
804                 result = c.release();
805         }
806         if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
807             ProcessingInstruction* pi = static_cast<ProcessingInstruction*>(container);
808             String data(pi->data());
809             data.remove(startOffset, endOffset - startOffset);
810             pi->setData(data, ec);
811         }
812         break;
813     case Node::ELEMENT_NODE:
814     case Node::ATTRIBUTE_NODE:
815     case Node::ENTITY_REFERENCE_NODE:
816     case Node::ENTITY_NODE:
817     case Node::DOCUMENT_NODE:
818     case Node::DOCUMENT_TYPE_NODE:
819     case Node::DOCUMENT_FRAGMENT_NODE:
820     case Node::NOTATION_NODE:
821     case Node::XPATH_NAMESPACE_NODE:
822     case Node::SHADOW_ROOT_NODE:
823         // FIXME: Should we assert that some nodes never appear here?
824         if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
825             if (fragment)
826                 result = fragment;
827             else
828                 result = container->cloneNode(false);
829         }
830 
831         Node* n = container->firstChild();
832         Vector<RefPtr<Node> > nodes;
833         for (unsigned i = startOffset; n && i; i--)
834             n = n->nextSibling();
835         for (unsigned i = startOffset; n && i < endOffset; i++, n = n->nextSibling())
836             nodes.append(n);
837 
838         processNodes(action, nodes, container, result, ec);
839         break;
840     }
841 
842     return result.release();
843 }
844 
processNodes(ActionType action,Vector<RefPtr<Node>> & nodes,PassRefPtr<Node> oldContainer,PassRefPtr<Node> newContainer,ExceptionCode & ec)845 void Range::processNodes(ActionType action, Vector<RefPtr<Node> >& nodes, PassRefPtr<Node> oldContainer, PassRefPtr<Node> newContainer, ExceptionCode& ec)
846 {
847     for (unsigned i = 0; i < nodes.size(); i++) {
848         switch (action) {
849         case DELETE_CONTENTS:
850             oldContainer->removeChild(nodes[i].get(), ec);
851             break;
852         case EXTRACT_CONTENTS:
853             newContainer->appendChild(nodes[i].release(), ec); // will remove n from its parent
854             break;
855         case CLONE_CONTENTS:
856             newContainer->appendChild(nodes[i]->cloneNode(true), ec);
857             break;
858         }
859     }
860 }
861 
processAncestorsAndTheirSiblings(ActionType action,Node * container,ContentsProcessDirection direction,PassRefPtr<Node> passedClonedContainer,Node * commonRoot,ExceptionCode & ec)862 PassRefPtr<Node> Range::processAncestorsAndTheirSiblings(ActionType action, Node* container, ContentsProcessDirection direction, PassRefPtr<Node> passedClonedContainer, Node* commonRoot, ExceptionCode& ec)
863 {
864     RefPtr<Node> clonedContainer = passedClonedContainer;
865     Vector<RefPtr<Node> > ancestors;
866     for (ContainerNode* n = container->parentNode(); n && n != commonRoot; n = n->parentNode())
867         ancestors.append(n);
868 
869     RefPtr<Node> firstChildInAncestorToProcess = direction == ProcessContentsForward ? container->nextSibling() : container->previousSibling();
870     for (Vector<RefPtr<Node> >::const_iterator it = ancestors.begin(); it != ancestors.end(); it++) {
871         RefPtr<Node> ancestor = *it;
872         if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
873             if (RefPtr<Node> clonedAncestor = ancestor->cloneNode(false)) { // Might have been removed already during mutation event.
874                 clonedAncestor->appendChild(clonedContainer, ec);
875                 clonedContainer = clonedAncestor;
876             }
877         }
878 
879         // Copy siblings of an ancestor of start/end containers
880         // FIXME: This assertion may fail if DOM is modified during mutation event
881         // FIXME: Share code with Range::processNodes
882         ASSERT(!firstChildInAncestorToProcess || firstChildInAncestorToProcess->parentNode() == ancestor);
883 
884         NodeVector nodes;
885         for (Node* child = firstChildInAncestorToProcess.get(); child;
886             child = (direction == ProcessContentsForward) ? child->nextSibling() : child->previousSibling())
887             nodes.append(child);
888 
889         for (NodeVector::const_iterator it = nodes.begin(); it != nodes.end(); it++) {
890             Node* child = it->get();
891             switch (action) {
892             case DELETE_CONTENTS:
893                 ancestor->removeChild(child, ec);
894                 break;
895             case EXTRACT_CONTENTS: // will remove child from ancestor
896                 if (direction == ProcessContentsForward)
897                     clonedContainer->appendChild(child, ec);
898                 else
899                     clonedContainer->insertBefore(child, clonedContainer->firstChild(), ec);
900                 break;
901             case CLONE_CONTENTS:
902                 if (direction == ProcessContentsForward)
903                     clonedContainer->appendChild(child->cloneNode(true), ec);
904                 else
905                     clonedContainer->insertBefore(child->cloneNode(true), clonedContainer->firstChild(), ec);
906                 break;
907             }
908         }
909         firstChildInAncestorToProcess = direction == ProcessContentsForward ? ancestor->nextSibling() : ancestor->previousSibling();
910     }
911 
912     return clonedContainer.release();
913 }
914 
extractContents(ExceptionCode & ec)915 PassRefPtr<DocumentFragment> Range::extractContents(ExceptionCode& ec)
916 {
917     checkDeleteExtract(ec);
918     if (ec)
919         return 0;
920 
921     return processContents(EXTRACT_CONTENTS, ec);
922 }
923 
cloneContents(ExceptionCode & ec)924 PassRefPtr<DocumentFragment> Range::cloneContents(ExceptionCode& ec)
925 {
926     if (!m_start.container()) {
927         ec = INVALID_STATE_ERR;
928         return 0;
929     }
930 
931     return processContents(CLONE_CONTENTS, ec);
932 }
933 
insertNode(PassRefPtr<Node> prpNewNode,ExceptionCode & ec)934 void Range::insertNode(PassRefPtr<Node> prpNewNode, ExceptionCode& ec)
935 {
936     RefPtr<Node> newNode = prpNewNode;
937 
938     ec = 0;
939 
940     if (!m_start.container()) {
941         ec = INVALID_STATE_ERR;
942         return;
943     }
944 
945     if (!newNode) {
946         ec = NOT_FOUND_ERR;
947         return;
948     }
949 
950     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
951     // the Range is read-only.
952     if (containedByReadOnly()) {
953         ec = NO_MODIFICATION_ALLOWED_ERR;
954         return;
955     }
956 
957     // HIERARCHY_REQUEST_ERR: Raised if the container of the start of the Range is of a type that
958     // does not allow children of the type of newNode or if newNode is an ancestor of the container.
959 
960     // an extra one here - if a text node is going to split, it must have a parent to insert into
961     bool startIsText = m_start.container()->isTextNode();
962     if (startIsText && !m_start.container()->parentNode()) {
963         ec = HIERARCHY_REQUEST_ERR;
964         return;
965     }
966 
967     // In the case where the container is a text node, we check against the container's parent, because
968     // text nodes get split up upon insertion.
969     Node* checkAgainst;
970     if (startIsText)
971         checkAgainst = m_start.container()->parentNode();
972     else
973         checkAgainst = m_start.container();
974 
975     Node::NodeType newNodeType = newNode->nodeType();
976     int numNewChildren;
977     if (newNodeType == Node::DOCUMENT_FRAGMENT_NODE) {
978         // check each child node, not the DocumentFragment itself
979         numNewChildren = 0;
980         for (Node* c = newNode->firstChild(); c; c = c->nextSibling()) {
981             if (!checkAgainst->childTypeAllowed(c->nodeType())) {
982                 ec = HIERARCHY_REQUEST_ERR;
983                 return;
984             }
985             ++numNewChildren;
986         }
987     } else {
988         numNewChildren = 1;
989         if (!checkAgainst->childTypeAllowed(newNodeType)) {
990             ec = HIERARCHY_REQUEST_ERR;
991             return;
992         }
993     }
994 
995     for (Node* n = m_start.container(); n; n = n->parentNode()) {
996         if (n == newNode) {
997             ec = HIERARCHY_REQUEST_ERR;
998             return;
999         }
1000     }
1001 
1002     // INVALID_NODE_TYPE_ERR: Raised if newNode is an Attr, Entity, Notation, ShadowRoot or Document node.
1003     switch (newNodeType) {
1004     case Node::ATTRIBUTE_NODE:
1005     case Node::ENTITY_NODE:
1006     case Node::NOTATION_NODE:
1007     case Node::DOCUMENT_NODE:
1008     case Node::SHADOW_ROOT_NODE:
1009         ec = RangeException::INVALID_NODE_TYPE_ERR;
1010         return;
1011     default:
1012         break;
1013     }
1014 
1015     bool collapsed = m_start == m_end;
1016     if (startIsText) {
1017         RefPtr<Text> newText = static_cast<Text*>(m_start.container())->splitText(m_start.offset(), ec);
1018         if (ec)
1019             return;
1020         m_start.container()->parentNode()->insertBefore(newNode.release(), newText.get(), ec);
1021         if (ec)
1022             return;
1023 
1024         // This special case doesn't seem to match the DOM specification, but it's currently required
1025         // to pass Acid3. We might later decide to remove this.
1026         if (collapsed)
1027             m_end.setToBeforeChild(newText.get());
1028     } else {
1029         RefPtr<Node> lastChild;
1030         if (collapsed)
1031             lastChild = (newNodeType == Node::DOCUMENT_FRAGMENT_NODE) ? newNode->lastChild() : newNode;
1032 
1033         int startOffset = m_start.offset();
1034         m_start.container()->insertBefore(newNode.release(), m_start.container()->childNode(startOffset), ec);
1035         if (ec)
1036             return;
1037 
1038         // This special case doesn't seem to match the DOM specification, but it's currently required
1039         // to pass Acid3. We might later decide to remove this.
1040         if (collapsed)
1041             m_end.set(m_start.container(), startOffset + numNewChildren, lastChild.get());
1042     }
1043 }
1044 
toString(ExceptionCode & ec) const1045 String Range::toString(ExceptionCode& ec) const
1046 {
1047     if (!m_start.container()) {
1048         ec = INVALID_STATE_ERR;
1049         return String();
1050     }
1051 
1052     Vector<UChar> result;
1053 
1054     Node* pastLast = pastLastNode();
1055     for (Node* n = firstNode(); n != pastLast; n = n->traverseNextNode()) {
1056         if (n->nodeType() == Node::TEXT_NODE || n->nodeType() == Node::CDATA_SECTION_NODE) {
1057             String data = static_cast<CharacterData*>(n)->data();
1058             int length = data.length();
1059             int start = (n == m_start.container()) ? min(max(0, m_start.offset()), length) : 0;
1060             int end = (n == m_end.container()) ? min(max(start, m_end.offset()), length) : length;
1061             result.append(data.characters() + start, end - start);
1062         }
1063     }
1064 
1065     return String::adopt(result);
1066 }
1067 
toHTML() const1068 String Range::toHTML() const
1069 {
1070     return createMarkup(this);
1071 }
1072 
text() const1073 String Range::text() const
1074 {
1075     if (!m_start.container())
1076         return String();
1077 
1078     // We need to update layout, since plainText uses line boxes in the render tree.
1079     // FIXME: As with innerText, we'd like this to work even if there are no render objects.
1080     m_start.container()->document()->updateLayout();
1081 
1082     return plainText(this);
1083 }
1084 
createContextualFragment(const String & markup,ExceptionCode & ec) const1085 PassRefPtr<DocumentFragment> Range::createContextualFragment(const String& markup, ExceptionCode& ec) const
1086 {
1087     if (!m_start.container()) {
1088         ec = INVALID_STATE_ERR;
1089         return 0;
1090     }
1091 
1092     Node* element = m_start.container()->isElementNode() ? m_start.container() : m_start.container()->parentNode();
1093     if (!element || !element->isHTMLElement()) {
1094         ec = NOT_SUPPORTED_ERR;
1095         return 0;
1096     }
1097 
1098     // Logic from deprecatedCreateContextualFragment should just be moved into
1099     // this function.  Range::createContextualFragment semantics do not make
1100     // sense for the rest of the DOM implementation to use.
1101     RefPtr<DocumentFragment> fragment = toHTMLElement(element)->deprecatedCreateContextualFragment(markup);
1102     if (!fragment) {
1103         ec = NOT_SUPPORTED_ERR;
1104         return 0;
1105     }
1106 
1107     return fragment.release();
1108 }
1109 
1110 
detach(ExceptionCode & ec)1111 void Range::detach(ExceptionCode& ec)
1112 {
1113     // Check first to see if we've already detached:
1114     if (!m_start.container()) {
1115         ec = INVALID_STATE_ERR;
1116         return;
1117     }
1118 
1119     m_ownerDocument->detachRange(this);
1120 
1121     m_start.clear();
1122     m_end.clear();
1123 }
1124 
checkNodeWOffset(Node * n,int offset,ExceptionCode & ec) const1125 Node* Range::checkNodeWOffset(Node* n, int offset, ExceptionCode& ec) const
1126 {
1127     switch (n->nodeType()) {
1128         case Node::DOCUMENT_TYPE_NODE:
1129         case Node::ENTITY_NODE:
1130         case Node::NOTATION_NODE:
1131             ec = RangeException::INVALID_NODE_TYPE_ERR;
1132             return 0;
1133         case Node::CDATA_SECTION_NODE:
1134         case Node::COMMENT_NODE:
1135         case Node::TEXT_NODE:
1136             if (static_cast<unsigned>(offset) > static_cast<CharacterData*>(n)->length())
1137                 ec = INDEX_SIZE_ERR;
1138             return 0;
1139         case Node::PROCESSING_INSTRUCTION_NODE:
1140             if (static_cast<unsigned>(offset) > static_cast<ProcessingInstruction*>(n)->data().length())
1141                 ec = INDEX_SIZE_ERR;
1142             return 0;
1143         case Node::ATTRIBUTE_NODE:
1144         case Node::DOCUMENT_FRAGMENT_NODE:
1145         case Node::DOCUMENT_NODE:
1146         case Node::ELEMENT_NODE:
1147         case Node::ENTITY_REFERENCE_NODE:
1148         case Node::XPATH_NAMESPACE_NODE:
1149         case Node::SHADOW_ROOT_NODE: {
1150             if (!offset)
1151                 return 0;
1152             Node* childBefore = n->childNode(offset - 1);
1153             if (!childBefore)
1154                 ec = INDEX_SIZE_ERR;
1155             return childBefore;
1156         }
1157     }
1158     ASSERT_NOT_REACHED();
1159     return 0;
1160 }
1161 
checkNodeBA(Node * n,ExceptionCode & ec) const1162 void Range::checkNodeBA(Node* n, ExceptionCode& ec) const
1163 {
1164     // INVALID_NODE_TYPE_ERR: Raised if the root container of refNode is not an
1165     // Attr, Document, DocumentFragment or ShadowRoot node, or part of a SVG shadow DOM tree,
1166     // or if refNode is a Document, DocumentFragment, ShadowRoot, Attr, Entity, or Notation node.
1167 
1168     switch (n->nodeType()) {
1169         case Node::ATTRIBUTE_NODE:
1170         case Node::DOCUMENT_FRAGMENT_NODE:
1171         case Node::DOCUMENT_NODE:
1172         case Node::ENTITY_NODE:
1173         case Node::NOTATION_NODE:
1174         case Node::SHADOW_ROOT_NODE:
1175             ec = RangeException::INVALID_NODE_TYPE_ERR;
1176             return;
1177         case Node::CDATA_SECTION_NODE:
1178         case Node::COMMENT_NODE:
1179         case Node::DOCUMENT_TYPE_NODE:
1180         case Node::ELEMENT_NODE:
1181         case Node::ENTITY_REFERENCE_NODE:
1182         case Node::PROCESSING_INSTRUCTION_NODE:
1183         case Node::TEXT_NODE:
1184         case Node::XPATH_NAMESPACE_NODE:
1185             break;
1186     }
1187 
1188     Node* root = n;
1189     while (ContainerNode* parent = root->parentNode())
1190         root = parent;
1191 
1192     switch (root->nodeType()) {
1193         case Node::ATTRIBUTE_NODE:
1194         case Node::DOCUMENT_NODE:
1195         case Node::DOCUMENT_FRAGMENT_NODE:
1196         case Node::SHADOW_ROOT_NODE:
1197             break;
1198         case Node::CDATA_SECTION_NODE:
1199         case Node::COMMENT_NODE:
1200         case Node::DOCUMENT_TYPE_NODE:
1201         case Node::ELEMENT_NODE:
1202         case Node::ENTITY_NODE:
1203         case Node::ENTITY_REFERENCE_NODE:
1204         case Node::NOTATION_NODE:
1205         case Node::PROCESSING_INSTRUCTION_NODE:
1206         case Node::TEXT_NODE:
1207         case Node::XPATH_NAMESPACE_NODE:
1208             if (root->isSVGShadowRoot())
1209                 break;
1210             ec = RangeException::INVALID_NODE_TYPE_ERR;
1211             return;
1212     }
1213 }
1214 
cloneRange(ExceptionCode & ec) const1215 PassRefPtr<Range> Range::cloneRange(ExceptionCode& ec) const
1216 {
1217     if (!m_start.container()) {
1218         ec = INVALID_STATE_ERR;
1219         return 0;
1220     }
1221 
1222     return Range::create(m_ownerDocument, m_start.container(), m_start.offset(), m_end.container(), m_end.offset());
1223 }
1224 
setStartAfter(Node * refNode,ExceptionCode & ec)1225 void Range::setStartAfter(Node* refNode, ExceptionCode& ec)
1226 {
1227     if (!m_start.container()) {
1228         ec = INVALID_STATE_ERR;
1229         return;
1230     }
1231 
1232     if (!refNode) {
1233         ec = NOT_FOUND_ERR;
1234         return;
1235     }
1236 
1237     if (refNode->document() != m_ownerDocument) {
1238         ec = WRONG_DOCUMENT_ERR;
1239         return;
1240     }
1241 
1242     ec = 0;
1243     checkNodeBA(refNode, ec);
1244     if (ec)
1245         return;
1246 
1247     setStart(refNode->parentNode(), refNode->nodeIndex() + 1, ec);
1248 }
1249 
setEndBefore(Node * refNode,ExceptionCode & ec)1250 void Range::setEndBefore(Node* refNode, ExceptionCode& ec)
1251 {
1252     if (!m_start.container()) {
1253         ec = INVALID_STATE_ERR;
1254         return;
1255     }
1256 
1257     if (!refNode) {
1258         ec = NOT_FOUND_ERR;
1259         return;
1260     }
1261 
1262     if (refNode->document() != m_ownerDocument) {
1263         ec = WRONG_DOCUMENT_ERR;
1264         return;
1265     }
1266 
1267     ec = 0;
1268     checkNodeBA(refNode, ec);
1269     if (ec)
1270         return;
1271 
1272     setEnd(refNode->parentNode(), refNode->nodeIndex(), ec);
1273 }
1274 
setEndAfter(Node * refNode,ExceptionCode & ec)1275 void Range::setEndAfter(Node* refNode, ExceptionCode& ec)
1276 {
1277     if (!m_start.container()) {
1278         ec = INVALID_STATE_ERR;
1279         return;
1280     }
1281 
1282     if (!refNode) {
1283         ec = NOT_FOUND_ERR;
1284         return;
1285     }
1286 
1287     if (refNode->document() != m_ownerDocument) {
1288         ec = WRONG_DOCUMENT_ERR;
1289         return;
1290     }
1291 
1292     ec = 0;
1293     checkNodeBA(refNode, ec);
1294     if (ec)
1295         return;
1296 
1297     setEnd(refNode->parentNode(), refNode->nodeIndex() + 1, ec);
1298 
1299 }
1300 
selectNode(Node * refNode,ExceptionCode & ec)1301 void Range::selectNode(Node* refNode, ExceptionCode& ec)
1302 {
1303     if (!m_start.container()) {
1304         ec = INVALID_STATE_ERR;
1305         return;
1306     }
1307 
1308     if (!refNode) {
1309         ec = NOT_FOUND_ERR;
1310         return;
1311     }
1312 
1313     // INVALID_NODE_TYPE_ERR: Raised if an ancestor of refNode is an Entity, Notation or
1314     // DocumentType node or if refNode is a Document, DocumentFragment, ShadowRoot, Attr, Entity, or Notation
1315     // node.
1316     for (ContainerNode* anc = refNode->parentNode(); anc; anc = anc->parentNode()) {
1317         switch (anc->nodeType()) {
1318             case Node::ATTRIBUTE_NODE:
1319             case Node::CDATA_SECTION_NODE:
1320             case Node::COMMENT_NODE:
1321             case Node::DOCUMENT_FRAGMENT_NODE:
1322             case Node::DOCUMENT_NODE:
1323             case Node::ELEMENT_NODE:
1324             case Node::ENTITY_REFERENCE_NODE:
1325             case Node::PROCESSING_INSTRUCTION_NODE:
1326             case Node::TEXT_NODE:
1327             case Node::XPATH_NAMESPACE_NODE:
1328             case Node::SHADOW_ROOT_NODE:
1329                 break;
1330             case Node::DOCUMENT_TYPE_NODE:
1331             case Node::ENTITY_NODE:
1332             case Node::NOTATION_NODE:
1333                 ec = RangeException::INVALID_NODE_TYPE_ERR;
1334                 return;
1335         }
1336     }
1337 
1338     switch (refNode->nodeType()) {
1339         case Node::CDATA_SECTION_NODE:
1340         case Node::COMMENT_NODE:
1341         case Node::DOCUMENT_TYPE_NODE:
1342         case Node::ELEMENT_NODE:
1343         case Node::ENTITY_REFERENCE_NODE:
1344         case Node::PROCESSING_INSTRUCTION_NODE:
1345         case Node::TEXT_NODE:
1346         case Node::XPATH_NAMESPACE_NODE:
1347             break;
1348         case Node::ATTRIBUTE_NODE:
1349         case Node::DOCUMENT_FRAGMENT_NODE:
1350         case Node::DOCUMENT_NODE:
1351         case Node::ENTITY_NODE:
1352         case Node::NOTATION_NODE:
1353         case Node::SHADOW_ROOT_NODE:
1354             ec = RangeException::INVALID_NODE_TYPE_ERR;
1355             return;
1356     }
1357 
1358     if (m_ownerDocument != refNode->document())
1359         setDocument(refNode->document());
1360 
1361     ec = 0;
1362     setStartBefore(refNode, ec);
1363     if (ec)
1364         return;
1365     setEndAfter(refNode, ec);
1366 }
1367 
selectNodeContents(Node * refNode,ExceptionCode & ec)1368 void Range::selectNodeContents(Node* refNode, ExceptionCode& ec)
1369 {
1370     if (!m_start.container()) {
1371         ec = INVALID_STATE_ERR;
1372         return;
1373     }
1374 
1375     if (!refNode) {
1376         ec = NOT_FOUND_ERR;
1377         return;
1378     }
1379 
1380     // INVALID_NODE_TYPE_ERR: Raised if refNode or an ancestor of refNode is an Entity, Notation
1381     // or DocumentType node.
1382     for (Node* n = refNode; n; n = n->parentNode()) {
1383         switch (n->nodeType()) {
1384             case Node::ATTRIBUTE_NODE:
1385             case Node::CDATA_SECTION_NODE:
1386             case Node::COMMENT_NODE:
1387             case Node::DOCUMENT_FRAGMENT_NODE:
1388             case Node::DOCUMENT_NODE:
1389             case Node::ELEMENT_NODE:
1390             case Node::ENTITY_REFERENCE_NODE:
1391             case Node::PROCESSING_INSTRUCTION_NODE:
1392             case Node::TEXT_NODE:
1393             case Node::XPATH_NAMESPACE_NODE:
1394             case Node::SHADOW_ROOT_NODE:
1395                 break;
1396             case Node::DOCUMENT_TYPE_NODE:
1397             case Node::ENTITY_NODE:
1398             case Node::NOTATION_NODE:
1399                 ec = RangeException::INVALID_NODE_TYPE_ERR;
1400                 return;
1401         }
1402     }
1403 
1404     if (m_ownerDocument != refNode->document())
1405         setDocument(refNode->document());
1406 
1407     m_start.setToStartOfNode(refNode);
1408     m_end.setToEndOfNode(refNode);
1409 }
1410 
surroundContents(PassRefPtr<Node> passNewParent,ExceptionCode & ec)1411 void Range::surroundContents(PassRefPtr<Node> passNewParent, ExceptionCode& ec)
1412 {
1413     RefPtr<Node> newParent = passNewParent;
1414 
1415     if (!m_start.container()) {
1416         ec = INVALID_STATE_ERR;
1417         return;
1418     }
1419 
1420     if (!newParent) {
1421         ec = NOT_FOUND_ERR;
1422         return;
1423     }
1424 
1425     // INVALID_NODE_TYPE_ERR: Raised if node is an Attr, Entity, DocumentType, Notation,
1426     // Document, or DocumentFragment node.
1427     switch (newParent->nodeType()) {
1428         case Node::ATTRIBUTE_NODE:
1429         case Node::DOCUMENT_FRAGMENT_NODE:
1430         case Node::DOCUMENT_NODE:
1431         case Node::DOCUMENT_TYPE_NODE:
1432         case Node::ENTITY_NODE:
1433         case Node::NOTATION_NODE:
1434             ec = RangeException::INVALID_NODE_TYPE_ERR;
1435             return;
1436         case Node::CDATA_SECTION_NODE:
1437         case Node::COMMENT_NODE:
1438         case Node::ELEMENT_NODE:
1439         case Node::ENTITY_REFERENCE_NODE:
1440         case Node::PROCESSING_INSTRUCTION_NODE:
1441         case Node::TEXT_NODE:
1442         case Node::XPATH_NAMESPACE_NODE:
1443         case Node::SHADOW_ROOT_NODE:
1444             break;
1445     }
1446 
1447     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
1448     // the Range is read-only.
1449     if (containedByReadOnly()) {
1450         ec = NO_MODIFICATION_ALLOWED_ERR;
1451         return;
1452     }
1453 
1454     // Raise a HIERARCHY_REQUEST_ERR if m_start.container() doesn't accept children like newParent.
1455     Node* parentOfNewParent = m_start.container();
1456 
1457     // If m_start.container() is a character data node, it will be split and it will be its parent that will
1458     // need to accept newParent (or in the case of a comment, it logically "would" be inserted into the parent,
1459     // although this will fail below for another reason).
1460     if (parentOfNewParent->isCharacterDataNode())
1461         parentOfNewParent = parentOfNewParent->parentNode();
1462     if (!parentOfNewParent || !parentOfNewParent->childTypeAllowed(newParent->nodeType())) {
1463         ec = HIERARCHY_REQUEST_ERR;
1464         return;
1465     }
1466 
1467     if (m_start.container() == newParent || m_start.container()->isDescendantOf(newParent.get())) {
1468         ec = HIERARCHY_REQUEST_ERR;
1469         return;
1470     }
1471 
1472     // FIXME: Do we need a check if the node would end up with a child node of a type not
1473     // allowed by the type of node?
1474 
1475     // BAD_BOUNDARYPOINTS_ERR: Raised if the Range partially selects a non-Text node.
1476     Node* startNonTextContainer = m_start.container();
1477     if (startNonTextContainer->nodeType() == Node::TEXT_NODE)
1478         startNonTextContainer = startNonTextContainer->parentNode();
1479     Node* endNonTextContainer = m_end.container();
1480     if (endNonTextContainer->nodeType() == Node::TEXT_NODE)
1481         endNonTextContainer = endNonTextContainer->parentNode();
1482     if (startNonTextContainer != endNonTextContainer) {
1483         ec = RangeException::BAD_BOUNDARYPOINTS_ERR;
1484         return;
1485     }
1486 
1487     ec = 0;
1488     while (Node* n = newParent->firstChild()) {
1489         toContainerNode(newParent.get())->removeChild(n, ec);
1490         if (ec)
1491             return;
1492     }
1493     RefPtr<DocumentFragment> fragment = extractContents(ec);
1494     if (ec)
1495         return;
1496     insertNode(newParent, ec);
1497     if (ec)
1498         return;
1499     newParent->appendChild(fragment.release(), ec);
1500     if (ec)
1501         return;
1502     selectNode(newParent.get(), ec);
1503 }
1504 
setStartBefore(Node * refNode,ExceptionCode & ec)1505 void Range::setStartBefore(Node* refNode, ExceptionCode& ec)
1506 {
1507     if (!m_start.container()) {
1508         ec = INVALID_STATE_ERR;
1509         return;
1510     }
1511 
1512     if (!refNode) {
1513         ec = NOT_FOUND_ERR;
1514         return;
1515     }
1516 
1517     if (refNode->document() != m_ownerDocument) {
1518         ec = WRONG_DOCUMENT_ERR;
1519         return;
1520     }
1521 
1522     ec = 0;
1523     checkNodeBA(refNode, ec);
1524     if (ec)
1525         return;
1526 
1527     setStart(refNode->parentNode(), refNode->nodeIndex(), ec);
1528 }
1529 
checkDeleteExtract(ExceptionCode & ec)1530 void Range::checkDeleteExtract(ExceptionCode& ec)
1531 {
1532     if (!m_start.container()) {
1533         ec = INVALID_STATE_ERR;
1534         return;
1535     }
1536 
1537     ec = 0;
1538     if (!commonAncestorContainer(ec) || ec)
1539         return;
1540 
1541     Node* pastLast = pastLastNode();
1542     for (Node* n = firstNode(); n != pastLast; n = n->traverseNextNode()) {
1543         if (n->isReadOnlyNode()) {
1544             ec = NO_MODIFICATION_ALLOWED_ERR;
1545             return;
1546         }
1547         if (n->nodeType() == Node::DOCUMENT_TYPE_NODE) {
1548             ec = HIERARCHY_REQUEST_ERR;
1549             return;
1550         }
1551     }
1552 
1553     if (containedByReadOnly()) {
1554         ec = NO_MODIFICATION_ALLOWED_ERR;
1555         return;
1556     }
1557 }
1558 
containedByReadOnly() const1559 bool Range::containedByReadOnly() const
1560 {
1561     for (Node* n = m_start.container(); n; n = n->parentNode()) {
1562         if (n->isReadOnlyNode())
1563             return true;
1564     }
1565     for (Node* n = m_end.container(); n; n = n->parentNode()) {
1566         if (n->isReadOnlyNode())
1567             return true;
1568     }
1569     return false;
1570 }
1571 
firstNode() const1572 Node* Range::firstNode() const
1573 {
1574     if (!m_start.container())
1575         return 0;
1576     if (m_start.container()->offsetInCharacters())
1577         return m_start.container();
1578     if (Node* child = m_start.container()->childNode(m_start.offset()))
1579         return child;
1580     if (!m_start.offset())
1581         return m_start.container();
1582     return m_start.container()->traverseNextSibling();
1583 }
1584 
editingStartPosition() const1585 Position Range::editingStartPosition() const
1586 {
1587     // This function is used by range style computations to avoid bugs like:
1588     // <rdar://problem/4017641> REGRESSION (Mail): you can only bold/unbold a selection starting from end of line once
1589     // It is important to skip certain irrelevant content at the start of the selection, so we do not wind up
1590     // with a spurious "mixed" style.
1591 
1592     VisiblePosition visiblePosition = Position(m_start.container(), m_start.offset(), Position::PositionIsOffsetInAnchor);
1593     if (visiblePosition.isNull())
1594         return Position();
1595 
1596     ExceptionCode ec = 0;
1597     // if the selection is a caret, just return the position, since the style
1598     // behind us is relevant
1599     if (collapsed(ec))
1600         return visiblePosition.deepEquivalent();
1601 
1602     // if the selection starts just before a paragraph break, skip over it
1603     if (isEndOfParagraph(visiblePosition))
1604         return visiblePosition.next().deepEquivalent().downstream();
1605 
1606     // otherwise, make sure to be at the start of the first selected node,
1607     // instead of possibly at the end of the last node before the selection
1608     return visiblePosition.deepEquivalent().downstream();
1609 }
1610 
shadowTreeRootNode() const1611 Node* Range::shadowTreeRootNode() const
1612 {
1613     return startContainer() ? startContainer()->shadowTreeRootNode() : 0;
1614 }
1615 
pastLastNode() const1616 Node* Range::pastLastNode() const
1617 {
1618     if (!m_start.container() || !m_end.container())
1619         return 0;
1620     if (m_end.container()->offsetInCharacters())
1621         return m_end.container()->traverseNextSibling();
1622     if (Node* child = m_end.container()->childNode(m_end.offset()))
1623         return child;
1624     return m_end.container()->traverseNextSibling();
1625 }
1626 
boundingBox()1627 IntRect Range::boundingBox()
1628 {
1629     IntRect result;
1630     Vector<IntRect> rects;
1631     textRects(rects);
1632     const size_t n = rects.size();
1633     for (size_t i = 0; i < n; ++i)
1634         result.unite(rects[i]);
1635     return result;
1636 }
1637 
textRects(Vector<IntRect> & rects,bool useSelectionHeight)1638 void Range::textRects(Vector<IntRect>& rects, bool useSelectionHeight)
1639 {
1640     Node* startContainer = m_start.container();
1641     Node* endContainer = m_end.container();
1642 
1643     if (!startContainer || !endContainer)
1644         return;
1645 
1646     Node* stopNode = pastLastNode();
1647     for (Node* node = firstNode(); node != stopNode; node = node->traverseNextNode()) {
1648         RenderObject* r = node->renderer();
1649         if (!r || !r->isText())
1650             continue;
1651         RenderText* renderText = toRenderText(r);
1652         int startOffset = node == startContainer ? m_start.offset() : 0;
1653         int endOffset = node == endContainer ? m_end.offset() : numeric_limits<int>::max();
1654         renderText->absoluteRectsForRange(rects, startOffset, endOffset, useSelectionHeight);
1655     }
1656 }
1657 
textQuads(Vector<FloatQuad> & quads,bool useSelectionHeight) const1658 void Range::textQuads(Vector<FloatQuad>& quads, bool useSelectionHeight) const
1659 {
1660     Node* startContainer = m_start.container();
1661     Node* endContainer = m_end.container();
1662 
1663     if (!startContainer || !endContainer)
1664         return;
1665 
1666     Node* stopNode = pastLastNode();
1667     for (Node* node = firstNode(); node != stopNode; node = node->traverseNextNode()) {
1668         RenderObject* r = node->renderer();
1669         if (!r || !r->isText())
1670             continue;
1671         RenderText* renderText = toRenderText(r);
1672         int startOffset = node == startContainer ? m_start.offset() : 0;
1673         int endOffset = node == endContainer ? m_end.offset() : numeric_limits<int>::max();
1674         renderText->absoluteQuadsForRange(quads, startOffset, endOffset, useSelectionHeight);
1675     }
1676 }
1677 
1678 #ifndef NDEBUG
1679 #define FormatBufferSize 1024
formatForDebugger(char * buffer,unsigned length) const1680 void Range::formatForDebugger(char* buffer, unsigned length) const
1681 {
1682     String result;
1683     String s;
1684 
1685     if (!m_start.container() || !m_end.container())
1686         result = "<empty>";
1687     else {
1688         char s[FormatBufferSize];
1689         result += "from offset ";
1690         result += String::number(m_start.offset());
1691         result += " of ";
1692         m_start.container()->formatForDebugger(s, FormatBufferSize);
1693         result += s;
1694         result += " to offset ";
1695         result += String::number(m_end.offset());
1696         result += " of ";
1697         m_end.container()->formatForDebugger(s, FormatBufferSize);
1698         result += s;
1699     }
1700 
1701     strncpy(buffer, result.utf8().data(), length - 1);
1702 }
1703 #undef FormatBufferSize
1704 #endif
1705 
areRangesEqual(const Range * a,const Range * b)1706 bool areRangesEqual(const Range* a, const Range* b)
1707 {
1708     if (a == b)
1709         return true;
1710     if (!a || !b)
1711         return false;
1712     return a->startPosition() == b->startPosition() && a->endPosition() == b->endPosition();
1713 }
1714 
rangeOfContents(Node * node)1715 PassRefPtr<Range> rangeOfContents(Node* node)
1716 {
1717     ASSERT(node);
1718     RefPtr<Range> range = Range::create(node->document());
1719     int exception = 0;
1720     range->selectNodeContents(node, exception);
1721     return range.release();
1722 }
1723 
maxStartOffset() const1724 int Range::maxStartOffset() const
1725 {
1726     if (!m_start.container())
1727         return 0;
1728     if (!m_start.container()->offsetInCharacters())
1729         return m_start.container()->childNodeCount();
1730     return m_start.container()->maxCharacterOffset();
1731 }
1732 
maxEndOffset() const1733 int Range::maxEndOffset() const
1734 {
1735     if (!m_end.container())
1736         return 0;
1737     if (!m_end.container()->offsetInCharacters())
1738         return m_end.container()->childNodeCount();
1739     return m_end.container()->maxCharacterOffset();
1740 }
1741 
boundaryNodeChildrenChanged(RangeBoundaryPoint & boundary,ContainerNode * container)1742 static inline void boundaryNodeChildrenChanged(RangeBoundaryPoint& boundary, ContainerNode* container)
1743 {
1744     if (!boundary.childBefore())
1745         return;
1746     if (boundary.container() != container)
1747         return;
1748     boundary.invalidateOffset();
1749 }
1750 
nodeChildrenChanged(ContainerNode * container)1751 void Range::nodeChildrenChanged(ContainerNode* container)
1752 {
1753     ASSERT(container);
1754     ASSERT(container->document() == m_ownerDocument);
1755     boundaryNodeChildrenChanged(m_start, container);
1756     boundaryNodeChildrenChanged(m_end, container);
1757 }
1758 
boundaryNodeChildrenWillBeRemoved(RangeBoundaryPoint & boundary,ContainerNode * container)1759 static inline void boundaryNodeChildrenWillBeRemoved(RangeBoundaryPoint& boundary, ContainerNode* container)
1760 {
1761     for (Node* nodeToBeRemoved = container->firstChild(); nodeToBeRemoved; nodeToBeRemoved = nodeToBeRemoved->nextSibling()) {
1762         if (boundary.childBefore() == nodeToBeRemoved) {
1763             boundary.setToStartOfNode(container);
1764             return;
1765         }
1766 
1767         for (Node* n = boundary.container(); n; n = n->parentNode()) {
1768             if (n == nodeToBeRemoved) {
1769                 boundary.setToStartOfNode(container);
1770                 return;
1771             }
1772         }
1773     }
1774 }
1775 
nodeChildrenWillBeRemoved(ContainerNode * container)1776 void Range::nodeChildrenWillBeRemoved(ContainerNode* container)
1777 {
1778     ASSERT(container);
1779     ASSERT(container->document() == m_ownerDocument);
1780     boundaryNodeChildrenWillBeRemoved(m_start, container);
1781     boundaryNodeChildrenWillBeRemoved(m_end, container);
1782 }
1783 
boundaryNodeWillBeRemoved(RangeBoundaryPoint & boundary,Node * nodeToBeRemoved)1784 static inline void boundaryNodeWillBeRemoved(RangeBoundaryPoint& boundary, Node* nodeToBeRemoved)
1785 {
1786     if (boundary.childBefore() == nodeToBeRemoved) {
1787         boundary.childBeforeWillBeRemoved();
1788         return;
1789     }
1790 
1791     for (Node* n = boundary.container(); n; n = n->parentNode()) {
1792         if (n == nodeToBeRemoved) {
1793             boundary.setToBeforeChild(nodeToBeRemoved);
1794             return;
1795         }
1796     }
1797 }
1798 
nodeWillBeRemoved(Node * node)1799 void Range::nodeWillBeRemoved(Node* node)
1800 {
1801     ASSERT(node);
1802     ASSERT(node->document() == m_ownerDocument);
1803     ASSERT(node != m_ownerDocument);
1804     ASSERT(node->parentNode());
1805     boundaryNodeWillBeRemoved(m_start, node);
1806     boundaryNodeWillBeRemoved(m_end, node);
1807 }
1808 
boundaryTextInserted(RangeBoundaryPoint & boundary,Node * text,unsigned offset,unsigned length)1809 static inline void boundaryTextInserted(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
1810 {
1811     if (boundary.container() != text)
1812         return;
1813     unsigned boundaryOffset = boundary.offset();
1814     if (offset >= boundaryOffset)
1815         return;
1816     boundary.setOffset(boundaryOffset + length);
1817 }
1818 
textInserted(Node * text,unsigned offset,unsigned length)1819 void Range::textInserted(Node* text, unsigned offset, unsigned length)
1820 {
1821     ASSERT(text);
1822     ASSERT(text->document() == m_ownerDocument);
1823     boundaryTextInserted(m_start, text, offset, length);
1824     boundaryTextInserted(m_end, text, offset, length);
1825 }
1826 
boundaryTextRemoved(RangeBoundaryPoint & boundary,Node * text,unsigned offset,unsigned length)1827 static inline void boundaryTextRemoved(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
1828 {
1829     if (boundary.container() != text)
1830         return;
1831     unsigned boundaryOffset = boundary.offset();
1832     if (offset >= boundaryOffset)
1833         return;
1834     if (offset + length >= boundaryOffset)
1835         boundary.setOffset(offset);
1836     else
1837         boundary.setOffset(boundaryOffset - length);
1838 }
1839 
textRemoved(Node * text,unsigned offset,unsigned length)1840 void Range::textRemoved(Node* text, unsigned offset, unsigned length)
1841 {
1842     ASSERT(text);
1843     ASSERT(text->document() == m_ownerDocument);
1844     boundaryTextRemoved(m_start, text, offset, length);
1845     boundaryTextRemoved(m_end, text, offset, length);
1846 }
1847 
boundaryTextNodesMerged(RangeBoundaryPoint & boundary,NodeWithIndex & oldNode,unsigned offset)1848 static inline void boundaryTextNodesMerged(RangeBoundaryPoint& boundary, NodeWithIndex& oldNode, unsigned offset)
1849 {
1850     if (boundary.container() == oldNode.node())
1851         boundary.set(oldNode.node()->previousSibling(), boundary.offset() + offset, 0);
1852     else if (boundary.container() == oldNode.node()->parentNode() && boundary.offset() == oldNode.index())
1853         boundary.set(oldNode.node()->previousSibling(), offset, 0);
1854 }
1855 
textNodesMerged(NodeWithIndex & oldNode,unsigned offset)1856 void Range::textNodesMerged(NodeWithIndex& oldNode, unsigned offset)
1857 {
1858     ASSERT(oldNode.node());
1859     ASSERT(oldNode.node()->document() == m_ownerDocument);
1860     ASSERT(oldNode.node()->parentNode());
1861     ASSERT(oldNode.node()->isTextNode());
1862     ASSERT(oldNode.node()->previousSibling());
1863     ASSERT(oldNode.node()->previousSibling()->isTextNode());
1864     boundaryTextNodesMerged(m_start, oldNode, offset);
1865     boundaryTextNodesMerged(m_end, oldNode, offset);
1866 }
1867 
boundaryTextNodesSplit(RangeBoundaryPoint & boundary,Text * oldNode)1868 static inline void boundaryTextNodesSplit(RangeBoundaryPoint& boundary, Text* oldNode)
1869 {
1870     if (boundary.container() != oldNode)
1871         return;
1872     unsigned boundaryOffset = boundary.offset();
1873     if (boundaryOffset <= oldNode->length())
1874         return;
1875     boundary.set(oldNode->nextSibling(), boundaryOffset - oldNode->length(), 0);
1876 }
1877 
textNodeSplit(Text * oldNode)1878 void Range::textNodeSplit(Text* oldNode)
1879 {
1880     ASSERT(oldNode);
1881     ASSERT(oldNode->document() == m_ownerDocument);
1882     ASSERT(oldNode->parentNode());
1883     ASSERT(oldNode->isTextNode());
1884     ASSERT(oldNode->nextSibling());
1885     ASSERT(oldNode->nextSibling()->isTextNode());
1886     boundaryTextNodesSplit(m_start, oldNode);
1887     boundaryTextNodesSplit(m_end, oldNode);
1888 }
1889 
expand(const String & unit,ExceptionCode & ec)1890 void Range::expand(const String& unit, ExceptionCode& ec)
1891 {
1892     VisiblePosition start(startPosition());
1893     VisiblePosition end(endPosition());
1894     if (unit == "word") {
1895         start = startOfWord(start);
1896         end = endOfWord(end);
1897     } else if (unit == "sentence") {
1898         start = startOfSentence(start);
1899         end = endOfSentence(end);
1900     } else if (unit == "block") {
1901         start = startOfParagraph(start);
1902         end = endOfParagraph(end);
1903     } else if (unit == "document") {
1904         start = startOfDocument(start);
1905         end = endOfDocument(end);
1906     } else
1907         return;
1908     setStart(start.deepEquivalent().containerNode(), start.deepEquivalent().computeOffsetInContainerNode(), ec);
1909     setEnd(end.deepEquivalent().containerNode(), end.deepEquivalent().computeOffsetInContainerNode(), ec);
1910 }
1911 
getClientRects() const1912 PassRefPtr<ClientRectList> Range::getClientRects() const
1913 {
1914     if (!m_start.container())
1915         return 0;
1916 
1917     m_ownerDocument->updateLayoutIgnorePendingStylesheets();
1918 
1919     Vector<FloatQuad> quads;
1920     getBorderAndTextQuads(quads);
1921 
1922     return ClientRectList::create(quads);
1923 }
1924 
getBoundingClientRect() const1925 PassRefPtr<ClientRect> Range::getBoundingClientRect() const
1926 {
1927     FloatRect rect = boundingRect();
1928     return rect.isEmpty() ? 0 : ClientRect::create(rect);
1929 }
1930 
adjustFloatQuadsForScrollAndAbsoluteZoomAndPageScale(Vector<FloatQuad> & quads,Document * document,RenderObject * renderer)1931 static void adjustFloatQuadsForScrollAndAbsoluteZoomAndPageScale(Vector<FloatQuad>& quads, Document* document, RenderObject* renderer)
1932 {
1933     FrameView* view = document->view();
1934     if (!view)
1935         return;
1936 
1937     float pageScale = 1;
1938     if (Page* page = document->page()) {
1939         if (Frame* frame = page->mainFrame())
1940             pageScale = frame->pageScaleFactor();
1941     }
1942 
1943     IntRect visibleContentRect = view->visibleContentRect();
1944     for (size_t i = 0; i < quads.size(); ++i) {
1945         quads[i].move(-visibleContentRect.x(), -visibleContentRect.y());
1946         adjustFloatQuadForAbsoluteZoom(quads[i], renderer);
1947         if (pageScale != 1)
1948             adjustFloatQuadForPageScale(quads[i], pageScale);
1949     }
1950 }
1951 
getBorderAndTextQuads(Vector<FloatQuad> & quads) const1952 void Range::getBorderAndTextQuads(Vector<FloatQuad>& quads) const
1953 {
1954     Node* startContainer = m_start.container();
1955     Node* endContainer = m_end.container();
1956     Node* stopNode = pastLastNode();
1957 
1958     HashSet<Node*> nodeSet;
1959     for (Node* node = firstNode(); node != stopNode; node = node->traverseNextNode()) {
1960         if (node->isElementNode())
1961             nodeSet.add(node);
1962     }
1963 
1964     for (Node* node = firstNode(); node != stopNode; node = node->traverseNextNode()) {
1965         if (node->isElementNode()) {
1966             if (!nodeSet.contains(node->parentNode())) {
1967                 if (RenderBoxModelObject* renderBoxModelObject = static_cast<Element*>(node)->renderBoxModelObject()) {
1968                     Vector<FloatQuad> elementQuads;
1969                     renderBoxModelObject->absoluteQuads(elementQuads);
1970                     adjustFloatQuadsForScrollAndAbsoluteZoomAndPageScale(elementQuads, m_ownerDocument.get(), renderBoxModelObject);
1971 
1972                     quads.append(elementQuads);
1973                 }
1974             }
1975         } else if (node->isTextNode()) {
1976             if (RenderObject* renderer = static_cast<Text*>(node)->renderer()) {
1977                 RenderText* renderText = toRenderText(renderer);
1978                 int startOffset = (node == startContainer) ? m_start.offset() : 0;
1979                 int endOffset = (node == endContainer) ? m_end.offset() : INT_MAX;
1980 
1981                 Vector<FloatQuad> textQuads;
1982                 renderText->absoluteQuadsForRange(textQuads, startOffset, endOffset);
1983                 adjustFloatQuadsForScrollAndAbsoluteZoomAndPageScale(textQuads, m_ownerDocument.get(), renderText);
1984 
1985                 quads.append(textQuads);
1986             }
1987         }
1988     }
1989 }
1990 
1991 
boundingRect() const1992 FloatRect Range::boundingRect() const
1993 {
1994     if (!m_start.container())
1995         return FloatRect();
1996 
1997     m_ownerDocument->updateLayoutIgnorePendingStylesheets();
1998 
1999     Vector<FloatQuad> quads;
2000     getBorderAndTextQuads(quads);
2001     if (quads.isEmpty())
2002         return FloatRect();
2003 
2004     FloatRect result;
2005     for (size_t i = 0; i < quads.size(); ++i)
2006         result.unite(quads[i].boundingBox());
2007 
2008     return result;
2009 }
2010 
2011 } // namespace WebCore
2012 
2013 #ifndef NDEBUG
2014 
showTree(const WebCore::Range * range)2015 void showTree(const WebCore::Range* range)
2016 {
2017     if (range && range->boundaryPointsValid()) {
2018         range->startContainer()->showTreeAndMark(range->startContainer(), "S", range->endContainer(), "E");
2019         fprintf(stderr, "start offset: %d, end offset: %d\n", range->startOffset(), range->endOffset());
2020     }
2021 }
2022 
2023 #endif
2024